Mastering Algorithms With C - Kyle Loudon [204]
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 has the smallest shortest-path estimate among the white vertices. We color this vertex black where it resides in the list of adjacency-list structures. Next, we traverse the vertices adjacent to the selected vertex. As we traverse each vertex, we look up its color and shortest-path estimate in the list of adjacency-list structures. Once we have located this information, we call relax to relax the edge between the selected vertex and the adjacent vertex. If relax needs to update the shortest-path estimate and parent of the adjacent vertex, it does so where the adjacent vertex resides in the list of adjacency-list structures. We then repeat this process until all vertices have been colored black.
Once the main loop in Dijkstra's algorithm terminates, we are finished computing the shortest paths from the start vertex to all other vertices reachable from it in the graph. At this point, we insert each black PathVertex structure from the list of adjacency-list structures into the linked list paths. In paths, the parent of the start vertex is set to NULL. The parent member of every other vertex points to the vertex that precedes it in the shortest path from the start vertex. The weight member of each PathVertex structure is not populated because it is needed only for storing weights in adjacency lists. Figure 16.4 shows the list of PathVertex structures returned for the shortest paths computed in Figure 16.3.
Figure 16.4. The list returned by the operation shortest for the shortest paths computed in Figure 16.3
The runtime complexity of shortest is O (EV 2), where V is the number of vertices in the graph and E is the number of edges. This comes from the main loop, in which we select vertices and relax edges. For each of the V vertices we select, we first traverse V elements in the list of adjacency-list structures to determine which white vertex has the smallest shortest-path estimate. This part of the main loop is O (V 2) overall. Next, for each vertex adjacent to the vertex we select, the list of adjacency-list structures is consulted for the information needed to relax the edge between the two vertices. Over all V vertices that we select, the list is consulted E times, once for each of the E edges in all of the adjacency lists together. Each of these consultations requires O (V ) time to search the list. Therefore, for all V vertices that we select, an O (V ) operation is performed E times. Consequently, this part of the loop is O (EV 2), and the main loop overall is O (V 2 + EV 2), or O (EV 2). Since the loops before and after the main loop are O (V ), the runtime complexity of shortest is O (EV 2). However, recall that with a little improvement (similar to that discussed for Prim's algorithm at the end of the chapter), Dijkstra's algorithm can run in O (E lg V ) time.
Example 16.3. Implementation for Computing Shortest Paths
/****************************************************************************
* *
* ----------------------------- shortest.c ------------------------------ *
* *
****************************************************************************/
#include #include #include "graph.h" #include "graphalg.h" #include "list.h" #include "set.h" /***************************************************************************** * * * ---------------------------------