Mastering Algorithms with C

Implementation and Analysis of Shortest Paths

To compute the shortest paths from a vertex to all others reachable from it in a directed, weighted graph, the graph is represented in the same manner as described for minimum spanning trees. However, we use the PathVertex structure instead of MstVertex for vertices (see Example 16.3). The PathVertex structure allows us to represent weighted graphs as well as keep track of the information that Dijkstra’s algorithm requires for vertices and edges. The structure consists of five members: data is the data associated with the vertex, weight is the weight of the edge incident to the vertex, color is the color of the vertex, d is the shortest-path estimate for the vertex, and parent is the parent of the vertex in the shortest-paths tree. We build a graph consisting of PathVertex structures in the same manner as described for building graphs with MstVertex structures.

The shortest operation begins by initializing every vertex in the list of adjacency-list structures. We set the initial shortest-path estimate for each vertex to DBL_MAX, except the start vertex, whose estimate is set to 0.0. The vertex stored in each adjacency-list structure is used to maintain the color, shortest-path estimate, and parent of the vertex, for the same reasons as mentioned for computing minimum spanning trees.

At the center of Dijkstra’s algorithm is a single loop that iterates once for each vertex in the graph. We begin each iteration by selecting the vertex that ...