Shulou(Shulou.com)06/01 Report--

What is the shortest path algorithm of Dijkstra? I believe many inexperienced people don't know what to do about it. Therefore, this paper summarizes the causes and solutions of the problem. Through this article, I hope you can solve this problem.

01

-

Single source shortest path

First of all, explain what is the single-source shortest path, the so-called single-source shortest path is to specify a starting vertex and calculate the shortest path from that source point to all other vertices. As shown in the following figure, if the source point is set to A, then the single-source shortest path problem is to solve the shortest path from A to B, from A to C, from A to D, from A to E, and from A to F.

For example, the shortest path from A to D can be obtained by naked eye observation as follows: a-> C-> D, the distance is equal to 3-3-6, where the value 3 on the edge of A-> C is called weight, and it is known that this is an undirected graph, and the weight from C to An is also 3.

02

-

Finding the shortest path of single Source by Dijkstra algorithm

The algorithm first sets two sets, the S set and the V set. The S set initially has only the source vertices, that is, the vertices APowerVset is initially all vertices except the source vertices, as shown in the following illustration:

Set a cache dictionary from A to each vertex as the output of the algorithm, initially set to-1

Next, we begin to solve the first shortest distance from A to a node. Through the adjacency matrix, we can naturally find all the vertices connected to the existing edge of A, that is, vertex B and vertex C.

The Dijkstra algorithm will choose the one with the smallest distance A-> B-> C, select C and put it in the S set, but when updating the dist dictionary, the distance of A-> B and A-> C can be updated at the same time, as shown in the diagram below:

Further, find all the edges with which the last element of the S set, C, is associated with it in V: BMagne Dpi E, so

A-> B = 3 + 2 = 5

A-> D = 3 + 3 = 6

A-> E = 3 + 4 = 7

According to the Dijkstra algorithm, select the minimum distance, that is, B enters the S set, and the Dijkstra algorithm is compared with the A-> B distance in the dist dictionary.

If dist (A-> B)! =-1 and 5B), update dist (A-> B) = 5

If dist (A-> B)! =-1 and 5 > dist (A-> B), dist (A-> B) is not updated

Note that, according to this discussion, we actually consider two paths from A to B: a-> B, A-> C-> B, but there are more than these two paths to B, because you can also get to B through D, if there is a path smaller than the distance 5 in these roads, is there a loophole in the Dijkstra algorithm? This consideration is correct, but the Dijkstra algorithm assumes that the weight value of the edge must be greater than 0, which avoids that the path from D to B cannot be less than 5, because except A-> B, all other paths to B must pass through C, and among the vertices connected to C, B is the smallest, so after reaching B through other edges, the distance can not be less than 5.

The above analysis is the basic idea of the Dijkstra algorithm. Until the number of elements of set V is 0, the final dist dictionary is as follows:

03

-

Summary of Dijkstra algorithm

The basic idea of the algorithm:

1. Initialize two collections, the S collection and the V collection. The S set initially has only the source vertex, that is, the vertex APowerV set is initially all vertices except the source vertex, and the dist dictionary value is-1. Then, according to the adjacency matrix, find out the vertex list that has an edge with A, traverse the list, update the dist dictionary in turn (for example, list= {BMague C}, then update the dictionary key to the distance value of BMagazine C), find the vertex closest to A, and remove it from the V set to the S set.

two。 Catch the last element of the S set, according to the adjacency matrix, find out the vertex list with the edge in the V set, traverse the list, find the vertex with the smallest distance, and remove it from the V set to the S set.

3 dist update, discuss on a case-by-case basis, if the vertex traversed to is not the smallest vertex, then update the dist dictionary directly, such as list= {Djue E}, then update the dictionary key to the distance value of DMague E in turn. If the vertex traversed to is the smallest vertex, you need to judge the distance between dist [this vertex] and the current one. If the latter is small, update dist [this vertex], otherwise it will not be updated.

4. Repeat 2 and 3 until the V collection element is empty.

After reading the above, have you mastered what the Dijkstra shortest path algorithm is? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.