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