最短路径Dijkstra的图示化证明是怎么样的

本篇文章给大家分享的是有关最短路径Dijkstra的图示化证明是怎么样的，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。

先看图，后面分析

现在将图与之前学的最短路径证明算法联系起来。

首先起点A是水立刻到达的，假设剩下的一些点B,C,D,E,F全部是村庄，
那么此时遭受水淹的危险的村庄是与起点直接相连的2个节点B和C.
我们此时可以算出这2个节点与起点A的最短距离。
此时这2个节点中最短距离就是水最先淹没的村庄，在图中是B.
也就是过了3秒钟后，B被染成了黄色。

进入下一个阶段，既然B被淹没，此时与B直接相连的2个节点C和D都是下一步被淹没的村庄之一。
因为B的水正在向它们流动。
但是这里不要忘记A的水之前已经在向C流动了，
所以，我们称，与A和B系统直接相连的所有节点(C,D)是下一步可能遭受威胁的节点群。
这就是为什么当B被染成黄色后，要重新计算C先遭受B的水淹没的可能性大还是遭受A的水淹没的可能性大。放在算法里就是重新计算路径。

这里，C节点先遭受A的水淹没。那么此后B的水再来也无济于事，C已经被淹没了。

当C淹没后，与C直接相连的节点E也就被加入潜在淹没村庄群了。
此时潜在淹没村庄群的集合是(D,E).
此时就可以重新计算(D,E) 中每个节点通过已经淹没群(A,B,C)与A的距离。
实际上每次只要计算最后一个加入的节点对潜在淹没村庄群的影响就可以。

按照这样的思路，你是否对算法里的最短路径Dijkstra有了更深的理解了呢？
不用死记硬背了，真正从原理上理解！

以上就是最短路径Dijkstra的图示化证明是怎么样的，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注亿速云行业资讯频道。