文章内容概览
迪杰斯特拉算法
- Dijkstra（迪杰斯特拉）算法是驰名的图论算法
- Dijkstra算法解决有权图从一个节点到其它节点的最短门路问题
- 特点：“以终点为核心，向外层层扩大”
最短门路问题
假如有下图这样的一个网络，该网络有A、B、C、D、E、F这几个节点和若干条边，每条边都有相应的间隔。假如此时要求A到E的最短门路
下边列出由A到E的所有可能的门路以及门路长度
A->B->C->E = 13A->C->E = 11A->D->C->E =13A->D->E = 9A->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到各个顶点的最短距离
在疾速变动的技术中寻找不变，才是一个技术人的外围竞争力。知行合一，实践联合实际