Dijkstra算法解决最短路径问题

Dijkstra算法解决最短路径问题

狄克斯特拉（dijkstra）算法是解决最短路径（Short path）的经典算法，是荷兰计算机专家狄克斯特拉于1959年提出。实际中有很多应用：

例一、北京地铁从军事博物馆到光熙门，假设每站运行时间相同，怎么走最省时间？

例二、计算机网络中，内部网关协议（OSPF）寻找路由最短路径就是这种方法。

算法思想

输入（即已瞧露知条件）: 有权重的无向图G={E,V}，V是顶点的集合，E是边的集合 ，每一边皆有权重（大于零），源节点s和目的节点d都属于集合V（s∈V, d∈V）。

输出（即求得的结果）: 源节点s到所有其它节点的最短路径的长度。

初始化阶段，除了起点A外，所巨游有节点的距离dist设置为无穷大。

更新邻居的距离

起点A的邻居为为B，D，根据边AB、AD的权重，将其距离分别更新为

Distance(B)=2，Distance(D)=1

移除有最小距离的点D

由于A的邻居节点是B和D，Distance(B)=2>Distance(D)=1，所以移除D点。

以移除的D为起点进行更新

分别计算D的邻居节点的距离，等于AD的权重，加上DC、DFDG、DE、DB的权重。

移除B

在未移除的节点中，选择距离最小的B（ distance =2）移除，并且更新邻居

注意：distance(D) D不用更新，因为D已知称倘膨； distance(E)也不用更新，因为BD+DE=5，比前面计算的值3要大。

移除E

在未移除的节点中，选择距离最小的E（distance =3）移除，并且更新邻居

由于邻居B、D已经移除，所以不用更新； distance(G)也不用更新，因为BE+GE=16>distance(G)=5，比前面计算的值5要大。

移除C

在未移除的节点中，选择距离最小的C（distance =3）移除，并且更新邻居

移除G

最后移除F，并按前面原则更新各节点距离

到此，可以得到起点A到各个顶点的最短距离，完成了dijkstra的算法过程。