• Choose a category
• All
• Classic-Fiction

By Root 1544 0

white vertices in the graph, we select the vertex u with the smallest shortest-path estimate. Initially, this will be the start vertex since its shortest-path estimate is 0. After we select the vertex, we color it black. Next, for each white vertex v adjacent to u, we relax the edge (u, v). When we relax an edge, we determine whether going through u improves the shortest path computed thus far to v. To make this decision, we add the weight of (u, v) to the shortest-path estimate for u. If this value is less than or equal to the shortest-path estimate for v, we assign the value to v as its new shortest-path estimate, and we set the parent of v to u. We then repeat this process until all vertices have been colored black. Once we have computed the shortest-paths tree, the shortest path from s to another vertex t can be determined by starting at t in the tree and following successive parents until we reach s. The path in reverse is the shortest path from s to t.

Figure 16.3 illustrates the computation of the shortest paths between a and all other vertices in the graph. The shortest path from a to b, for example, is 〈 a, c, f, b 〉, which has a total weight of 7. The shortest-path estimate and parent of each vertex are displayed beside the vertex. The shortest-path estimate is to the left of the slash, and the parent is to the right. The edges shaded in light gray are the edges in the shortest-paths tree as it changes.

Figure 16.3. Computing shortest paths using Dijkstra's algorithm

Interface for Shortest Paths

Name

shortest

Synopsis

int shortest(Graph *graph, const PathVertex *start, List *paths, int (*match)

(const void *key1, const void *key2));

Return Value

0 if computing the shortest paths is successful, or -1 otherwise.

Description

Computes shortest paths between start and all other vertices in a directed, weighted graph specified by graph. The operation modifies graph, so a copy should be made before calling the operation, if necessary. Each vertex in graph must contain data of type PathVertex. Assign a weight to each edge by setting the weight member of the PathVertex structure passed as data2 to graph_ins_edge. Use the data member of each PathVertex structure to store data associated with the vertex, such as an identifier. The match function for graph, which is set by the caller when initializing the graph with graph_init, should compare only the data members of PathVertex structures. This is the same function that should be passed as the match argument to shortest. Once computed, information about the shortest paths is returned in paths, which is a list of PathVertex structures. 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 vertices in paths point to actual vertices in graph, so the caller must ensure that the storage in graph remains valid as long as paths is being accessed. Use list_destroy to destroy paths once it is no longer needed.

Complexity

O (EV 2), where V is the number of vertices in the graph and E is the number of edges. However, 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.

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