#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.
*/