What is the graphical proof of the shortest path Dijkstra

What this article shares with you is how the graphical proof of the shortest path Dijkstra is. The editor thinks it is very practical, so I share it with you. I hope you can get something after reading this article. Without saying much, let's take a look at it.

Look at the picture first, then analyze it later.

Now associate the graph with the shortest path proof algorithm you learned earlier.

First of all, the starting point An is that the water arrives immediately, assuming that some of the remaining points, B, C, D, D, and F, are all villages.

Then the villages in danger of flooding at this time are the two nodes B and C directly connected to the starting point.

At this point, we can calculate the shortest distance between the two nodes and the starting point A.

At this time, the shortest distance of the two nodes is the village where the water is the first to submerge, in the picture is B.

That is, after 3 seconds, B was dyed yellow.

Moving on to the next stage, since B is submerged, the two nodes C and D directly connected to B are one of the next submerged villages.

Because B's water is flowing towards them.

But don't forget here that A's water was already flowing to C before.

Therefore, we say that all the nodes directly connected to An and B systems (Cline D) are the node groups that may be threatened in the next step.

This is why when B is dyed yellow, it is necessary to recalculate whether C is more likely to be flooded by B or A first. To put it in the algorithm is to recalculate the path.

Here, node C is flooded by A. Then it is useless for B's water to come again after that. C has been submerged.

When C is submerged, the node E directly connected to C is also added to the potential submerged village group.

At this time, the set of potentially flooded village groups is (DJI E).

At this point, it is possible to recalculate the distance between each node and A through the inundated group (A ~ ~ B ~ C).

In fact, it is only necessary to calculate the impact of the last node on the potentially flooded village group each time.

In this way of thinking, do you have a better understanding of the shortest path Dijkstra in the algorithm?

There is no need to memorize, really understand from the principle!

The above is the graphical proof of the shortest path Dijkstra. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.