软考知识点——最短路径问题(迪杰斯特拉)算法
定义
所谓最短路径问题是指:如果从图中某一顶点(源点)到达另一顶点(终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边的权值总和(称为路径长度)达到最小。
Dijkstra(迪杰斯特拉)算法
他的算法思想是按路径长度递增的次序一步一步并入来求取,是贪心算法的一个应用,用来解决单源点到其余顶点的最短路径问题。
Dijkstra(迪杰斯特拉)算法示例:
第1步:初始化距离,其实指与D直接连接的点的距离。dis[c]代表D到C点的最短距离,因而初始dis[C]=3,dis[E]=4,dis[D]=0,其余为无穷大。设置集合S用来表示已经找到的最短路径。此时,S={D}。现在得到D到各点距离{D(0),C(3),E(4),F(),G(),B(),A()},其中代表未知数也可以说是无穷大,括号里面的数值代表D点到该点的最短距离。
第2步:不考虑集合S中的值,因为dis[C]=3,是当中距离最短的,所以此时更新S,S={D,C}。接着我们看与C连接的点,分别有B,E,F,已经在集合S中的不看,dis[C-B]=10,因而dis[B]=dis[C]+10=13,dis[F]=dis[C]+dis[C-F]=9,dis[E]=dis[C]+dis[C-E]=3+5=8>4(初始化时的dis[E]=4)不更新。此时{D(0),C(3),E(4),F(9),G(),B(13),A()}。
第3步:在第2步中,E点的值4最小,更新S={D,C,E},此时看与E点直接连接的点,分别有F,G。dis[F]=dis[E]+dis[E-F]=4+2=6(比原来的值小,得到更新),dis[G]=dis[E]+dis[E-G]=4+8=12(更新)。此时{D(0),C(3),E(4),F(6),G(12),B(13),A()}。
第4步:在第3步中,F点的值6最小,更新S={D,C,E,F},此时看与F点直接连接的点,分别有B,A,G。dis[B]=dis[F]+dis[F-B]=6+7=13,dis[A]=dis[F]+dis[F-A]=6+16=22,dis[G]=dis[F]+dis[F-G]=6+9=15>12(不更新)。此时{D(0),C(3),E(4),F(6),G(12),B(13),A(22)}.
第5步:在第4步中,G点的值12最小,更新S={D,C,E,F,G},此时看与G点直接连接的点,只有A。dis[A]=dis[G]+dis[G-A]=12+14=26>22(不更新)。{D(0),C(3),E(4),F(6),G(12),B(13),A(22)}.
第6步:在第5步中,B点的值13最小,更新S={D,C,E,F,G,B},此时看与B点直接连接的点,只有A。dis[A]=dis[B]+dis[B-A]=13+12=25>22(不更新)。{D(0),C(3),E(4),F(6),G(12),B(13),A(22)}.
第7步:最后只剩下A值,直接进入集合S={D,C,E,F,G,B,A},此时所有的点都已经遍历结束,得到最终结果{D(0),C(3),E(4),F(6),G(12),B(13),A(22)}.