共计 1251 个字符,预计需要花费 4 分钟才能阅读完成。
文章内容概览
迪杰斯特拉算法
- Dijkstra(迪杰斯特拉)算法是驰名的图论算法
- Dijkstra 算法解决有权图从一个节点到其它节点的 最短门路 问题
- 特点:“以终点为核心,向外层层扩大”
最短门路问题
假如有下图这样的一个网络,该网络有 A、B、C、D、E、F 这几个节点和若干条边,每条边都有相应的间隔。假如此时要求 A 到 E 的最短门路
下边列出由 A 到 E 的所有可能的门路以及门路长度
A->B->C->E = 13
A->C->E = 11
A->D->C->E =13
A->D->E = 9
A->F->E = 10
从列出的后果来看,最短的门路是 A ->D->E 这条,间隔是 9。这是人为的去查找的,然而咱们是须要将其转换成程序语言来解决求最短门路问题
先用文字介绍一下该算法的整个过程,而后再通过例子来解释每个过程
迪杰斯特拉算法
迪杰斯特拉算法过程形容
- 初始化两个汇合(S,U)(S 为只有初始顶点点 A 的汇合,U 为其它顶点的汇合)
- 如果 U 不为空,对 U 汇合顶点进行间隔的排序,并取出间隔 A 最近的一个顶点 D
- 将顶点 D 放入 S 汇合
- 更新通过顶点 D 达到 U 汇合所有点的间隔(如果间隔更小则更新,否则不更新)
- 反复步骤 2
- 直到 U 汇合为空,整个算法过程实现
通过下边的例子来了解上边的过程
因为要求 A 到 E 的最短距离,所以,首先将 A 纳入 S 汇合,且 A 到 A 的间隔为 0。而后其它顶点 U 的汇合就是 B、C、D、E、F,并计算 A 到这几个顶点的间隔,从图中能够看进去
因为汇合 U 不为空,所以对汇合 U 中,A 到各个顶点的间隔进行排序,找到到 A 的间隔最短的顶点,将其放入汇合 S。从图中能够看进去,A 到顶点 B 的间隔是最小的,所以将其放入汇合 S
而后应该计算: A 通过 B 达到其余各个顶点的间隔
因为晓得 B 到 C 的间隔为 5,所以 A 通过 B 达到 C 的间隔为:A->B->C = 6+5 = 11,因为原来汇合 U 中 A 到 C 的间隔为 9,9 < 11,所以,不须要更新到汇合 U 中,而后就失去下边这样的后果
而后再对 U 进行判断,发现不为空。所以对 U 中 A 到各个顶点的间隔再进行排序,发现 A 到 F 的间隔是最短的,此时就把到 F 放入到 S 汇合中。而后此时计算 A 通过 F 达到各个顶点的间隔。发现 A 通过 F 达到 E 的间隔为 10,此时,更新 U 中 A 到顶点 E 的间隔(原来这个间隔是不晓得的),然就失去如下后果
而后就是反复上边的步骤,发现 U 中距离最短的是 D,那么就把 D 放入到汇合 S,而后计算 A 通过 D 达到各个顶点的间隔,发现 A 通过 D 达到 C 的间隔为 11,A 通过 D 达到 E 的间隔是 9。此时发现 A 通过 D 达到 C 的间隔大于 U 中的 A 到 C 的间隔 9,所以不替换 U 中 A 到 C 的间隔。而后发现 A 通过 D 达到 E 的间隔 9,小于 U 中 A 到 E 的间隔 10,所以,替换掉 U 中 A 到 E 的值,那么就失去如下后果
而后汇合 U 中还剩两个元素(两个间隔值雷同,轻易选一个放入汇合 S),接着反复上边的步骤,直到汇合 U 为空。最终失去如下后果
失去的 S 汇合中的间隔就是 A 达到各个顶点的最短距离,以上便是迪杰斯特拉算法的整个过程。有趣味的话也能够推一个 B 到各个顶点的最短距离
在疾速变动的技术中寻找不变,才是一个技术人的外围竞争力。知行合一,实践联合实际