The shortest-path problem finds the path of shortest length connecting a starting vertex to each of the reachable vertices in the graph. The algorithm uses a breadth-first search of the vertices. Minimum path is a similar problem for weighted graphs. The problem determines a path of minimum weight from a starting vertex to each reachable vertex in the graph. As the graph in below figure illustrates, a shortest path may not be the minimum path. Assume A is the starting vertex and E is the reachable vertex. Three paths, A-B-E, A-C-E and A-D-E have path length 2, with weights 15, 17 and 13 respectively. The minimum path is A-C-D-E, with weight 11 but path length 3.
The Dijkstra algorithm solves the minimum-path problem. It uses a greedy strategy that solves the problem in stages. At each stage, we select the adjacent vertex x that defines a minimum path from the starting vertex. The term "greedy" indicates that the strategy attempts to maximum short-term gains, even through the decision might need to be reversed as we discover new vertices. In the sample graph in upper figure, we start at A and discover neighbors B, C and D. Vertices C and D defines path A-C and A-E having path weights 4 and 8, respectively. However, the path A-B has minimum weight among all of the neighbors of A. From vertex B, we discover its neighbor E using edge e(B, E) with weight 12. The total weight of path A-B-E is 15. We record our finding for vertex E that include the value 15 for the path weight and B as the parent. Latter, we discover that using C as an intermediate vertex yields a path A-C-E that connects A to E with a smaller path weight 14. Properties for E are updated to have a new path weight 14 and parent C. As new vertices are discovered, we continually make updates. In the end, we discover that the path A-C-D-E with weight 11 with weight 11 is the minimum path.
Designing the Dijkstra Algorithm :
The Dijkstra minimum-path algorithm uses the iterative strategy that we employed for the shortest-path problem, with one major difference. The search uses a minimum-priority queue rather than a queue to store the vertices. To define objects in the priority queue, we declare the static inner class MinInfo. A MinInfo object contains a vertex reference and the path weight as data members. The vertex is the ending vertex on a path from the starting vertex andpathWeight is sum of the weights for the edges of the path. The class implements the Comparable interface by defining compareTo() using the pathWeightattribute. This allows us to use the object in a priority queue.
Each step in the algorithm removes a MinInfo object from the priority queue and identifies the vertex. Because no subsequent step could find a new path to the vertex with a smaller weight, we have the minimum-path weight and can color the vertex BLACK(visited). The next action is to look at each of the neighbors of the vertex. For each neighbor that is not BLACK, check whether adding the edge to the minimum path from the starting vertex to the current vertex will create a path from the starting vertex to the neighbor that is "better" than any which have been determined previously. The data value for the neighbor vertex stores the minimum-path weight for any of the prior paths or is infinity when the neighbor is initially discovered. If the new path is better, create a MinInfo object with the neighbor and the total path weight as arguments and insert it into the priority queue. At the same time, update the data value and parent reference for the neighbor. The algorithm terminates whenever the priority queue becomes empty or when the number of visited vertices matches the vertex size of the graph. The priority queue could be come empty when a relatively small number of vertices are reachable from the starting vertex.
Let us illustrate the algorithm by using the upper graph, which is repeated by your reference. Vertex A is the starting vertex. To simplify notation, let MI(v, w) designate a MinInfo object with v as the ending vertex for path P(A, v) and with total path weight w. The algorithm begins with vertex A :
Setup:
Each iterative step pops a MinInfo object from the priority queue and identifies its vertex. If the edge from the vertex to a nonvisited neighbor creates a better path, updates occur to both data field and parent reference field of the neighbor. Each column in the table lists the data value and current parent reference for each vertex after any updates occur.
Step 1:
Step 2:
Step 3:
Step 4:
Step 5-6:
Why It Works :
To verify the Dijkstra algorithm results in a minimum path, assume that the algorithm finds a path from starting vertex vs to the ending vertex ve, which is not optimal. That is, a second path connects the vertices with a smaller weight. Assume this second path and the Dijkstra path are the same up to vertex u and that the weight of path P(vs, ve) found by Dijkstra's algorithm is W. The better (second) path has an intermediate vertex x that is in the priority queue but is not marked. The weight to x is :
w = weight for P(vs, x) = weight of P(vs, u) + weight (u, x)
The weight w must be less than W, so the MinInfo(x,w) object will come out of the priority queue before the path found by the algorithm. Continuing in this way, all the vertices on the better path will come out of the priority queue, and the algorithm will find the optimal path, contradicting our assumption that the algorithm does not find the minimum path :
Implementing the minimumPath() Method :
The method minimumPath() implements the Dijkstra algorithm. The method has the same signature as shortestPath(). The arguments are a graph and the starting vertex. The storage collection for MinInfo objects is the minimum-priority queue minPathPQ. The design of the algorithm is also modeled on the shortest-path algorithm. The boolean variables foundMinPath indicates when the minimum path is found. The search is an iterative process that uses a minimum-priority queue to store MinInfo objects.
- Running-Time Analysis
Coloring the vertices WHITE and initializing the dataValue field is O(V) operation. The actions in the loop "while(!minPathPQ.empty())" dominate the running time. In the worst case, the algorithm pushes all edges into the priority queue and pops all edges. Each push() and pop() operation is O(n log2 n), so the running time for all these priority-queue operations is O(E log2 E). Then we know :
The running time for Dijkstra's algorithm is thus O(V + E log2 V).
Minimum Path in Acyclic Graphs :
When the weighted digraph is acyclic, the problem of finding minimum paths is greatly simplified. The depth-first search creates a list of vertices in topological order :
dfsList:[v0, v1, ..., vn-1]
Assume vi is the starting vertex for the minimum-path problem. Vertices in the list v0 to vi-1 are not reachable from vi because a path from vi would indicate that the vertex has an earlier finishing time and so would come after vi in dfsList.
The algorithm begins at vi. After initializing the data value for all of the vertices to ∞, set the data value for vi to 0 and its parent reference to vi. This establishes a minimum path from vi to vi with weight 0. Iteratively scan the tail of the list. For each vertex v in the index [i,n), its data value is the minimum-path weight for any path from vi to v. If the value is ∞, then no path exists, and you proceed to the next vertex in the list. Otherwise, look at each neighbor w of v. We have found a path from vi to w that goes through v. The weight of this path is P(vi, v) + weight(v,w). Compare this weight with the weight of a previously discovered path from vi to w. The notation data(v) is the value of the data field for vertex v, which corresponds to the weight of a path from vi to v. Perform the comparison :
weight(P(vi, v) + (v, w)) = data(v) + weight(v,w) < data(w)
If the new path to w through v is better, update the data and parent reference fields for w. When the sequential scan concludes, the data field for each vertex has the minimum-path weight. For all reachable vertices, the parent reference field can be used to reconstruct the actual minimum path.
The method dagMinimumPath() implements the minimum-path algorithm for an acyclic graph. The method has parameters for the graph and the starting vertex :
A simple intuitive argument indicates why the algorithm works. At a vertex v in the sequential scan of dfsList, we use its current data value as the minimum-path weight from vi to v. This value, data(v), is the weight of the minimum path from vi to v. For there to be a better path, there must be an unvisited vertex, u, reachable from vi, that has an edge to v :
This is not possible, because topological order guarantees that u will come earlier in dfsList.
- Running-Time Analysis
The algorithm first creates a topological sort of the vertices with running time O(V+E). A loop visits all the vertices in the graph once and examines edges that emanate from each vertex only once. Access to all of the vertices and edges has running time O(V+E) and so the total running time for the algorithm is O(V+E).
Supplement :
* [ 資料結構 小學堂 ] 圖形結構 : 圖形最短路徑 (單點對全部頂點)
沒有留言:
張貼留言