The shortest path is probably the best to attract beginners in the various algorithms of the map - find the shortest road on the map may have tried each person. Below we use a computer to complete our "wish".
There is an interesting phenomenon in the algorithm of the figure, the greater the size of the problem, the more simple algorithm is. The figure is a complicated structure. For a specific problem, the result of solving the specific vertex will be affected by other vertices - a sphere that collides with each other, requires the state of the specific sphere, must consider the state of other spheres. Since each vertex is scanned, if you solve all the vertices, then the algorithm is very simple - not being traversed. However, when we reduce the size of the problem, that is natural, we hope that the scale of the algorithm is also reduced - if it does not decrease, isn't the killing chicken with a cow knife? However, it is because of the complexity of the graph, this reduction is not easy to achieve, so in order to reduce the scale of the algorithm, the algorithm is complicated.
In the following introduction, it is clear that the conclusions above are confirmed. The human cognitive process is from simple to complex, although the surface looks, seeking the shortest path between each vertex to complicate than the shortest path between the specific vertex to other vertices, but is like the above, essentially, The former is simpler. The following introduction does not consider historical factors (which means which algorithm is mentioned first), and does not consider the true thoughts of the algorithm. (Who is the reference or no reference, only from the connection between the algorithm itself Explain, please forgive me if you have omissions.
Ready to work
All the way, the picture class is very "bloated", in order to clearly explain the problem, it is necessary to "restart the stove to open", but also to separate the algorithm and the storage method for easy reuse.
First add several interfaces to the basic map class.
Template
Class network
{
PUBLIC:
INT FIND (const name & v) {int N; if (! Data.find (v, n)) Return -1; Return n;}
Dist & getE (int M, int N) {Return Data.Gete (m, n);}
Const dist & noedge () {return data.noedge;}
}
Template
Class Adjmatrix
{
PUBLIC:
Dist & getE (int M, int N) {return Edge [M] [N];
}
Template
Class Link
{
PUBLIC:
Dist & getE (int M, int N)
{
For (List
Iter! = Vertices [M] .E-> end () && iter-> VID IF (iter == Vertices [M] .E-> End ()) Return Noedge; IF (item-> vid == n) Return ITER-> Cost; Return noedge; } } Then, it is "calculated" "calculation" "" is tailored "for the shortest path algorithm. When you find the shortest path of a map, bind the figure to the algorithm, for example: Network Weight #include "network.h" Template Class weight { PUBLIC: Weight (Network { Length = new dist * [n]; path = new int * [n]; Shortest = new bool [n]; int i, j; For (i = 0; i { Length [i] = new dist (n]; path [i] = new int [n]; } For (i = 0; i { Shortest [i] = false; For (j = 0; j { Length [i] [j] = g-> get (i, j); IF (Length [i] [j]! = g-> noedge ()) PATH [I] [j] = i; ELSE PATH [I] [J] = -1; } } } ~ Weight () { For (int i = 0; i Delete [] length; delete [] path; delete [] shortest; } Private: Void Print (INT I, INT J) { IF (PATH [I] [J] == -1) cout << "no path" << endl; return; COUT << "Shortest Path:"; OUT (i, j); cout << g-> getv (j) << endl; COUT << "Path Length:" << Length [i] [j] << endl; } Void Out (Int i, int J) { IF (PATH [I]! = i) OUT (i, path [i] [j]); COUT << g-> getV (Path [i] [j]) << "->"; } Dist ** length; int ** path; bool * shortest; bool all; int N; Network } It is found that the constructor is really good, the initialization of the results of the algorithm and the algorithm itself have been opened, so that the basic steps of the algorithm are easy to see. The shortest path between all vertices (FLOYED algorithm) The path from V1 to V2 either V1-> V2, or in the middle through several vertices. Obviously we ask for the shortest one in these paths. In this way, the problem is very well solved - the origin is the source point to the purpose, then add the vertex, so that the path is gradually shortened, the vertices are added, the algorithm is over. Void allShortestPath () // folyed { IF (all) return; For (int K = 0; k { Shortest [K] = True; For (int i = 0; i For (int J = 0; j IF (Length [I] [K] Length [K] [J]) { Length [i] [j] = length [i] [k] length [k] [j]; Path [I] [J] = PATH [K] [J]; } } all = true; } Single source shortest path (Dijkstra algorithm) It is easy to find the following algorithm: Void ShortestPath (Int V1) { // Bellman-ford For (int K = 2; k For (int i = 0; i For (int J = 0; j IF (Length [V1] [J] Length [J] [i] { Length [v1] [i] = length [v1] [j] length [j] [i]; Path [V1] [i] = j; } } This is the Bellman-Ford algorithm, it can be seen that the idea of using the FLOYED algorithm can not make the algorithm's time complexity from O (N3) to the expected O (N2), but the spatial complexity is lowered from O (N2) to O (n), but this should also be, because only one line in the array is required. Therefore, I don't think this algorithm is to solve the "single source shortest path problem with the edge weight of arbitrary value" and is the "promotion" version of the Dijkstra algorithm. He is just the degraded version of the FLOYED algorithm. Obviously, the FLOYED algorithm is an iteration of N2 terraces to generate the shortest path; if we want to reduce the time complexity from o (N3) to the expected O (N2), the N2 edge of the N times it must change. For N-top, that is, only one side of each participating iteration - how the problem finds this side. Let's take a look at the weight of the weight. Assume that from the vertex 0, the distance to each vertex is A1, A2 ..., then the shortest distance AN must be the shortest distance from 0 to N. This is because if AN is not the shortest distance from 0 to N, then it is inevitably a vertex; but now the weight is not negated, one is more than the long side of this side, plus another A non-negative side is not possible than this side. From this principle, you can get the Dijkstra algorithm. Note that this and the Prim algorithm is extremely similar, don't know who to refer to who; but this is also inevitable, because their principles are the same. Void ShortestPath (Const Name & Vex1, Const Name & Vex2) // Dijkstra { INT V1 = g-> Find (vex1); int V2 = g-> Find (vex2); IF (Shortest [V1]) {Print (V1, V2); Return;} BOOL * S = New Bool [N]; INT I, J, K; For (i = 0; i { For (j = 0, k = v1; j IF (! S [J] &&length [V1] [J] S [k] = true; For (j = 0; j IF (! S [J] && Length [V1] [K] Length [K] [J] { Length [V1] [J] = Length [V1] [K] Length [K] [J]; PATH [V1] [J] = K; } } Shortest [V1] = true; print (v1, v2); } If the weight is negative, then the above principle is no longer applicable, and the Dijkstra algorithm is no longer applicable. At this time, there is no way, only accepts the O (N3) Bellman-Ford algorithm, although he can reduce o (n * e). However, why bother the weight of the side is negative? Or that sentence, reasonable is not easy. The shortest path between a specific two vertices (A * algorithm) In fact, this is our most concerned question. We just want to know how to get to the ground from A, don't want to know, how do I go to the A-A-A-A-Aland? Naturally, we hope that this algorithm has a time complexity of o (n), but it is not easy to achieve this goal like the FLOYED algorithm to change the Dijkstra algorithm. Let's first take a look at the time complexity of the shortest path between the Dijkstra calculation. Obviously, in the above Void ShortestPath (Const Name & VEX1, Const Name & VEX2), when S [V2] == True, the algorithm can be suspended. Assuming that the path between the two vertices is the shortest path between them (not needed to pass other intermediate vertices), and this path length is the shortest path in the shortest path of all destination points, then the first iteration When you get the result. That is to say, O (n). However, when the shortest path of the two vertices need to pass through other vertices, or the path length is not the shortest path in the shortest path of the source to the shortest path without the shortest path, then several iterations, corresponding, time complexity It turned into O (2N), O (3N) ... The last acquisition (iterative N-1 time) is O (N2). Obviously, the number of iterations is lower, and how many vertices should be passed on the shortest path, at least it iterates, we can only make the final iteration number close to the minimum number of needs. If we reducing the time complexity of the algorithm, we can only find ways to change the search range O (1), so that even if it is iterated, N-1 is obtained, that time complexity is still O (n). But this idea is achieved, but it is difficult. Still look at the Dijkstra algorithm, the first step is to look for a shortest path in the vertices in the S-in-S-Shan, this min operation uses the time complexity lower limit of the method based on the comparison is O (longn) (using the loser tree), then Each component of the scan results array is required to modify, and the time complexity here can only be o (n). The original Dijkstra calculation is not expected. Now let's add an additional condition - the shortcomings between the two points, that is, if there is a straight path between V1 and V2 (without other vertices), then this path is the shortest path between them. In this way, if the shortest path of V1 can be directly reached, the time complexity is O (1), it is obviously better than the original O (N) (here, it is actually O (logn)) improved. effectiveness. The generation of this change is because we have added additional conditions such as "the straight line between two points". In fact, a judgment criterion is introduced to reduce the original blind O (N) to O (1). This idea is the idea of a * algorithm. About a * algorithm more in-depth introduction, the information is limited, and everyone cannot meet everyone. Interested to go online, book, this kind of Chinese information is too small, everyone is ready to read the E-article. to sum up Unlike existing textbooks, I changed the order of the algorithm for shortest path to the above. I think this order really reflects the nature of the problem - when reducing the scale of the problem, in order to reduce the time complexity of the algorithm, you should find ways to narrow the search. The search range has been used to search for the direction of the greedy algorithm as much as possible to search closely to the last result. If we look back in the evolution of the algorithm, we can also get new conclusions. The Dijkstra algorithm actually doesn't have to do N2 search, comparison, and modification. When the vertices of the shortest path are determined, the search range has been reduced, just limited to the storage structure, which is not reflected in this reduction. If we make this range reduction directly, then use N times Dijkstra algorithm to replace the Floyed algorithm to increase efficiency. The A * algorithm is also the case, and if the A * algorithm for N points is used instead of the Dijkstra algorithm, it can also bring efficiency. However, the evolution of each step is actually accompanied by the introduction of additional conditions. From Floyed to Dijkstra, the weight is not negative, if this condition is not true, then it can only be degraded into a Bellman-Ford algorithm. From Dijkstra to A *, the introduction of additional judgment criteria (the shortline between two points), if this condition is not established, the same, only incomplete Dijkstra (seeking the purpose vertex end algorithm).
