## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required