迪杰斯特拉算法

应用场景-最短路径问题

看一个应用场景和问题:

1. 战争时期，胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从G点出发，需要分别把邮件分别送到 A, B, C , D, E, F 六个村庄
2. 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里
3. 问：如何计算出G村庄到 其它各个村庄的最短距离?
4. 如果从其它点出发到各个点的最短距离又是多少?

迪杰斯特拉(Dijkstra)算法介绍

迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个结点到其他结点的最短举例。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。

迪杰斯特拉(Dijkstra)算法过程

设置触发顶点为v,顶点集合V{v1,v2,vi...},v到V中各顶点的距离构成距离集合Dis,Dis{d1,d2,di...},Dis集合记录着v到图中各顶点的距离(到自身可以看作0,v到vi距离对应di)

1. 从Dis中选择值最小的di并移出Dis集合,同时移出V集合中对应的顶点vi,此时的v到vi即为最短路径。
2. 更新Dis集合,更新规则为: 比较v到V集合中顶点的距离值,与v通过vi到V集合中顶点的距离值,保留值较小的一个(同时也应该更新顶点的前驱结点为vi,表明是通过vi到到达的)
3. 重复执行两步骤,直到最短路径顶点目标顶点即可结束