In this question, give a direction to G, each side has a non-negative length (cost) A [i] [j], the length of the path is the length of the side of this path. . For a given source top point S, you need to find the shortest path from it to the other vertices (called purposes) in the figure. Figures 13-10a show a presentation map having five vertices, the number of each side is the length. Suppose the source vertex S is 1, the shortest path from the vertex 1 Press the path length sequence in Figures 13-10B, and the numbers in front of each path are the length of the path.
The greedy algorithm invented by E. Dijkstra can solve the shortest path problem, which results in the shortest path by step by step. Each step produces a shortest path to the new destination vertex. The purpose of the purpose can be achieved next, select the vertex of the shortest path length in the vertex of the shortest path in the shortest path. That is, the method of D i J k S T R a generates the shortest path in the path length sequence.
First, initially generated the path from S to its own, this path is not side, its length is 0. In each step of the greedy algorithm, the next shortest path is generated. One method is to add a possible shortest side in the shortest path currently generated, and the resulting new path is the originally generated shortest path plus one side. This strategy does not always work. Another method is to consider the shortest side of each of the shortest paths, and then select the shortest one from all of these edges, this policy is the D i J k S T R A algorithm.
When the shortest path is generated in length, the next shortest path is always formed by plus one of the shortest paths that have been generated. In fact, the next shortest path is always expanded from the shortest path to the shortest path, and the shortest path thereofged by this path has not yet been generated. For example, in Fig. 1 3 - 1 0, the second path is formed by the first path to expand a side; the third path is the second path to expand a side; the fourth path is the first path. Expand a side; the fifth path is the third path to expand a side.
The shortest path can be stored in a simple method by the above observation. You can use the array p, p [i] to give the vertex in front of the vertex I of the vertex I in the path of I to the path. In this example, P [1: 5] = [0, 1, 1, 3, 4]. The path from S to the vertex I can be created in reverse. From I, press P [I], P [P [P [P [P [P [P [P [P [I]]],., Until the vertices S or 0 is reached. In this example, if the vertex sequence begins in P [I] = 4, P [4] = 3, P [3] = 1 = S, so the path is 1, 3, 4, 5.
To make it easy to generate the shortest path in the order of length increment, define D [i] to add a shortest edge length in the shortest path that has been generated, so that the extension path reaches the vertex I. Initially, only a path from S to S is 0, at which time for each vertex I, D [I] or equal to A [S] [i] (A is a length adjacent matrix of a directed figure). To generate the next path, you need to select the next node that has not yet produced the shortest path, and the minimum D value is the end point of the next path in these nodes. When a new shortest path is obtained, a smaller D value may occur due to the new shortest path, so some of the D values of some vertices may change.
In summary, the pseudo code shown in Fig. 1 3-11 can be obtained, 1) initialize P to be initialized to S, this initialization is used to record the best information currently available. That is, from s to i's shortest path, that is, it is obtained by the path of S to it itself. When a shorter path is found, the P [I] value will be updated. If the next shortest path is generated, the value of D is updated according to the expansion of the path. 1) Initialization D [I] = a [S] [i] (1 ≤ i ≤ N),
For all vertex I adjacent to S, set P [I] = S, for the remaining vertices P [I] = 0;
Established a L table for all vertices of P [i] ≠ 0.
2) If L is empty, terminate, otherwise it will turn to 3).
3) Delete the smallest vertices of the D value from the L.
4) For all non-reached vertices J, update D [J] value is min {d [j], d [i] a [i] [j]}; if D [j] happens Change and J have not
In L, set P [j] = 1, and J to add L, turn to 2.
Figure 1 - 11 Description of the shortest path algorithm
1. Selection of data structure
We need to select a data structure for unreached vertices. You can select the smallest D value from the L. If l is maintained with the minimum pile (see 9.3), this selection can be completed within the log time. Due to 3) The number of execution is O (N), the time required is O (N L O g n). Since the new shortest path is expanded, the unreachable vertex may result in a smaller D value, so some D values may be required in 4). Although the reduction in the algorithm is not a standard minimum heap operation, it can be completed within the log time. Since the total number of minus operations is performed is: O (the number of edges in the figure) = O (N2), the total time of the reduction operation is O (N2 L O g n).
If the L is maintained by the unordered linked list, then 3) and 4) take the time of O (N2), 3), each execution of O (| L |) = O (N), each reduction operation The time required (1) (required to subtract the value of D [J], but the linked list does not have to change). The pseudo code of Fig. 1-1-1 is detailed as a procedural 1 3 - 5 using the disorderly linked table, which uses C H a I n (see programs 3 - 8) and C H A I n I t e R A T O R classes (see programs 3 - 1 8).
Program 13-5 shortest path program
Template
Void Adjacencywdigraph
:: ShortestPaths (Int S, T D [], INT P [])
{// Look for the shortest path from the vertex s, return to the shortest distance in D
// Return to the front point in P
IF (s <1 || s> n) throw outofbounds ();
Chain
L; // path can reach the list of vertices
Chainiterator
I;
// Initialization D, P, L
For (INT i = 1; i <= n; i ) {
D [i] = a [s] [i];
IF (d [i] == noedge) p [i] = 0;
Else {P [i] = S;
L. I n s e r t (0, i);}
}
// update D, P
While (! l.isempty ()) {// Looking for vertex v with minimum D
INT * v = I.initialize (L);
INT * w = i.next ();
While (w) {
IF (D [* W] // Remove the next shortest path to the vertex V in L and update D INT i = * V; L. D e l e t e (* v); For (int J = 1; j <= n; j ) { IF (a [i] [j]! = noedge && (! p [j] || D [j]> d [i] a [i] [j])) { // reduce D [J] D [j] = d [i] a [i] [j]; // Add J to L IF (! p [j]) l.insert (0, j); P [j] = i; } } } If N o E DGE is large enough, the length of no shortest path is greater than or equal to N o E DGE, the IF condition of the last FOR cycle can be simplified: IF (D [J]> D [i] a [i] [J])) NOEDGE value should be in the range that can make D [J] a [i] [J] will not produce overflow. 2. Complexity analysis The complexity of programs 1 3 - 5 is O (N2), and any shortest path algorithm must check at least once, because any side may be in the shortest path. Therefore, the minimum possible time of this algorithm is O (E). Due to the use of the consumable abutment matrix, only the time when which edge is in the figure, the time is required to be O (N2). Therefore, the algorithm of this description requires O (N2) time. However, the program 1 3 - 5 is optimized (constant factor level). Even if the adjacent table is changed, the total time of the last F O R cycle will be reduced to O (E) (because only the D value of the vertex adjacent to I). The total time required to select and delete the minimum distance from L is still O (N2). Reprinted from Shada Studio
