espero te la rifes programando por que pues... no jala corrigelo y si le corriges las fallas me lo mandas no??? gracias... bye
#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 ∈ V y z ∈ V; a es el vértice de origen y z el vértice de destino.
* Sea un conjunto C ⊂ 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 ← V
2. Para todo vértice i ∈ C, i ≠ a, se establece Di ← ∞ ; Da ← 0
3. Para todo vértice i ∈ C se establece Pi = a
4. Se obtiene el vértice s ∈ C tal que no existe otro vértice w ∈ C tal que Dw < Ds
* Si s = z entonces se ha terminado el algoritmo.
5. Se elimina de C el vértice s: C ← C−{s}
6. Para cada arista e ∈ A de longitud l, que une el vértice s con algún otro vértice t ∈ C,
* Si l+Ds < Dt, entonces:
1. Se establece Dt ← l+Ds
2. Se establece Pt ← 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.
*/