In the early morning of this morning, I don't know if you watched the twin star. My buddies in my dormitory, but I went to the cold. The newspaper will reach 200 when the peak is peak, huh, huh, it seems to be so exaggerated. The meteor is not so easy to be seen, so we have to keep up with your neck; if you are alcohol, you have to endure the bullous gum runway lying on the ground. But so hard is quite worth it, because the meteor is so beautiful! Especially the kind of very large, some flammuses, some white purple, when they fall, the northwest corner of Diaon; but more are small, they secretly slide through the horizon, you respond I haven't come, I don't want to be willing! It's tired, and the eyes spent, I fantasy to open the stars and galloping around each star. Hey, I suddenly want to ask you a very weird problem. If these stars have been connected to a network, the distance and fuel consumption of each tunnel are different, and you can only fly from the star tunnel. How should you find the most convenient path from A star to B? Hey, let me tell you about thinking. In fact, the interstellar model I just proposed is a typical picture (Graph). What is the picture? The picture is a limited collection, including a group of nodes (Vertex) and a side (EDGE) with weights that connect nodes into a network, and record it in the mathematical diagram of g = (v, e). Now come abstract our question: We are looking for a path to another node in a picture so that the sum of the weights walking along this path. In many algorithms for the shortest path, the most famous should be the Dijkstra algorithm. In the neutral class in our school, this algorithm made me feel fine. The following code is extracted from a C job, where the figure is represented by a two-dimensional oriented length width array. I deliberately delete the comment, see if you can understand it yourself. #include "iostream" #define Vexnum 6 # Define Infin 32767VOID Dijkstra (int (* thisgraph) [vexnum], int from, int to) {
INT dist (Vexnum], Path [Vexnum], isvisited [vexnum];
For (int i = 0; i Dist [i] = thisgraph [from] [I]; isvisited [i] = 0; if (i! = From && dist [i] } IsVisited [from] = 1; dist [from] = 0; for (i = 0; i INT min = infin; int u = from; for (int J = 0; j u = j; min = dist [j]; } Isvisited [u] = 1; for (int w = 0; W IF (! isvisited [W] && thisgraph [u] [w] } } } Std :: cout << "From" << from << "point to the shortest path of" << to << "point (from right to left):" << std :: end1; i = to; while (i! = from) { Std :: cout << i << "<-"; i = path [i]; } Std :: cout << i; std :: cout << std :: endl << "length is:" << dist [to]; } You combine to look at an example, this is a typical adjacency matrix of a figure: Infininfin10infin30100infininfinfinfininfinInfinInfinInfinfinfinfin10infinInfinInfin10infinInfinInfinInfinInfinInfinfin The Dijkstra algorithm is performed on the above figure, and the steps to obtain are: Point i = 1 i = 2 i = 3 i = 4 i = 5 1 infinInfinInfinInfinfin 210 0-> 2 3infin 60 0-> 2-> 350 0-> 4-> 3 430 0-> 430 0-> 4 5100 0 -> 5100 0-> 590 0-> 4-> 560 0-> 4-> 3-> 5 minimum 2 4 3 5 isvisited 0, 20, 2, 40, 2, 3, 40, 2, 3, 4, 5
