[prev] 19 [next]

Path Finding (cont)

BFS algorithm for finding shortest path:

int findPath(Graph g, Vertex src, Vertex dest)
{
   Vertex *path = malloc(nV(g) * sizeof(Vertex));
   int *visited = calloc(nV(g),sizeof(int));
   Queue q = newQueue();
   QueueJoin(q,src);
   int isFound = 0;
   while (!emptyQ(q) && !isFound) {
      Vertex y, x = QueueLeave(q);
      for (y = 0; y < nV(g); y++) {
         if (!hasEdge(g,x,y)) continue;

	 if (!visited[y])
            { path[y] = x; QueueJoin(q,y); visited[y] = 1; }

         if (y == dest) { isFound = 1; break; }
         
      }
   }
   if (isFound) {
      // display path in dest..src order
      Vertex v;
      for (v = dest; v != src; v = path[v])
          printf("%d-", v);
      printf("%d\n", src);
   }
   free(visited); free(path);
   return isFound;
}