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

What is the Dijkstra algorithm, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

Dijkstra algorithm is one of the algorithms for solving the single-source shortest path in the "graph". The so-called single-source shortest path means that a "initial node" is given and the shortest path to other vertices is solved.

For ease of description, assume that the weights of all edges in the graph are not negative:

The diagram is already concise and convenient to describe the algorithm.

Suppose Node 1 is the designated start node, and now we want the shortest path from Node 1 to Node 2, 3 and 4. The solving process of No.1 to No.2 nodes is as follows:

(1) since nodes 1 are directly connected to nodes 2, 3 and 4, the paths are W6, W5 and W1 respectively (we put these paths into a temporary set and try to choose the one with the shortest path to the other nodes).

(2) if W6 is the shortest path in the temporary set, then W6 is the final result, and the key problem is W1-> W4, W1-> W3-> w2, w5-> w2, w5-> W3-> W4 are also the other 4 paths. So we assume that W1 in (1) is the shortest path directly connected to Node 1 (so W1 is the shortest path of Node 1 and Node 4, and we put Node 4 into the final shortest path set).

(3) for Node 4, in addition to the directly connected Node 1, there are other Node 2 and Node 3. If the path sum of W1-> W4 is less than W6, then the shortest path of nodes 1 and 2 in the temporary collection needs to be updated to w1+w4 (assuming update). Similarly, the path sum of W1-> W3 is less than W5, then the shortest path of nodes 1 and 3 in the temporary set needs to be updated to w1+w3 (assuming the update, note that our goal is to find the shortest path from node 1 to node 2, but the algorithm will be accompanied by solving the shortest path to other nodes).

(4) so far, the shortest paths from No.1 node to No.2 node and Node 3 are saved in the temporary set, and now one of the shortest paths is selected according to the steps of (2), and the final result is if No.2 is selected. If Node 3 is selected, it is necessary to further judge if W1-> W3-> W2 path and less than W1-> W4, the final shortest path is updated to w1+w3+w2.

Note: the above is the whole process of the algorithm, and the prerequisite is that the weight is not negative. Then step (1) of the algorithm cannot be realized on the assumption that the weight may be negative, because it is impossible to select the node with the shortest path to other nodes in the first place (it can be assumed that W2 is negative, so W6 is not necessarily the shortest path). This is a prerequisite. Of course, when the algorithm is really implemented, we also need to consider the case of equal weight.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

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.