/* dijkstra.c Compute shortest paths in weighted graphs using Dijkstra's algorithm by: Steven Skiena date: March 6, 2002 */ /* Copyright 2003 by Steven S. Skiena; all rights reserved. Permission is granted for use in non-commerical applications provided this copyright notice remains intact and unchanged. This program appears in my book: "Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003. See our website www.programming-challenges.com for additional information. This book can be ordered from Amazon.com at http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/ */ #include #include "bool.h" #include "graph.h" #define MAXINT 100007 int parent[MAXV+1]; /* discovery relation */ dijkstra(graph *g, int start) /* WAS prim(g,start) */ { int i; /* counter */ edgenode *p; /* temporary pointer */ bool intree[MAXV+1]; /* is the vertex in the tree yet? */ int distance[MAXV+1]; /* distance vertex is from start */ int v; /* current vertex to process */ int w; /* candidate next vertex */ int weight; /* edge weight */ int dist; /* best current distance from start */ for (i=1; i<=g->nvertices; i++) { intree[i] = FALSE; distance[i] = MAXINT; parent[i] = -1; } distance[start] = 0; v = start; while (intree[v] == FALSE) { intree[v] = TRUE; p = g->edges[v]; while (p != NULL) { w = p->y; weight = p->weight; /* CHANGED */ if (distance[w] > (distance[v]+weight)) { /* CHANGED */ distance[w] = distance[v]+weight; /* CHANGED */ parent[w] = v; } p = p->next; } v = 1; dist = MAXINT; for (i=1; i<=g->nvertices; i++) if ((intree[i] == FALSE) && (dist > distance[i])) { dist = distance[i]; v = i; } } /*for (i=1; i<=g->nvertices; i++) printf("%d %d\n",i,distance[i]);*/ } main() { graph g; int i; read_graph(&g,FALSE); dijkstra(&g,1); for (i=1; i<=g.nvertices; i++) find_path(1,i,parent); printf("\n"); }