1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#define INFINITY    (MAX_INT - 1)
 
typedef struct {
    int weight;
    int dest;} DijkEdge;
 
typedef struct {
    DijkEdge* connections; /* Un array de arcos */
    int numconnect;    int distance;
    int isDead;
} Vertex;
 
void Dijkstra(Vertex* graph, int nodecount, int source) {    for(int i = 0; i < nodecount; i++) {
        if(i == source) {
            graph[i].distance = 0;
            graph[i].isDead = 0;
        } else {            graph[i].distance = INFINITY;
            graph[i].isDead = 0;
         }
    }
    for(int i = 0; i < nodecount; i++) {        int next;
        int min = INFINITY+1;
        for(int j = 0; j < nodecount; j++) {
            if(!graph[j].isDead && graph[j].distance < min) {
                next = j;                min = graph[j].distance;
            }
        }
        for(int j = 0; j < graph[next].numconnect; j++) {
            if(graph[graph[next].connections[j].dest].distance >               graph[next].distance + graph[next].connections[j].weight)
            {
                graph[graph[next].connections[j].dest].distance =
                    graph[next].distance + graph[next].connections[j].weight;
            }        }
        graph[next].isDead = 1;
    }
    for(int i = 0; i < nodecount; i++) {
        printf("The distance between nodes %i and %i is %i",            source, i, graph[i].distance);
    }
}
/*
    * Sea G=(V,A) un grafo dirigido y etiquetado.    * Sean los vértices a &#8712; V y z &#8712; V; a es el vértice de origen y z el vértice de destino.
    * Sea un conjunto C &#8834; V, que contiene los vértices de V cuyo camino más corto desde a todavía no se conoce.
    * Sea un vector D, con tantas dimensiones como elementos tiene V, y que “guardaâ€Â? las distancias entre a y cada uno de los vértices de V.
    * Sea, finalmente, otro vector, P, con las mismas dimensiones que D, y que conserva la información sobre qué vértice precede a cada uno de los vértices en el camino.
 El algoritmo para determinar el camino de longitud mínima entre los vértices a y z es:
 
   1. C &#8592; V
   2. Para todo vértice i &#8712; C, i &#8800; a, se establece Di &#8592; &#8734; ; Da &#8592; 0
   3. Para todo vértice i &#8712; C se establece Pi = a   4. Se obtiene el vértice s &#8712; C tal que no existe otro vértice w &#8712; C tal que Dw < Ds
          * Si s = z entonces se ha terminado el algoritmo.
   5. Se elimina de C el vértice s: C &#8592; C&#8722;{s}
   6. Para cada arista e &#8712; A de longitud l, que une el vértice s con algún otro vértice t &#8712; C,
          * Si l+Ds < Dt, entonces:               1. Se establece Dt &#8592; l+Ds
               2. Se establece Pt &#8592; s
   7. Se regresa al paso 4
 
Al terminar este algoritmo, en Dz estará guardada la distancia mínima entre a y z. Por otro lado, mediante el vector P se puede obtener el camino mínimo: en Pz estará y, el vértice que precede a z en el camino mínimo; en Py estará el que precede a y, y así sucesivamente, hasta llegar a a.*/