最短路径dijkstra算法

2744557306

最短路径

当图为带权图时，把一个从顶点V0到图中任意顶点的路径所经过边的权值之和，定义为该路径的带权长度，把带权路径长度最短的那条路径称为最短路径。

对于最短路径有下面两种说法：

5 o! z  ~7 f3 i6 B0 W

在最短路径中遇到不同的问题我们应该用那种方法呢？具体方法如下图所示：

& E" p8 _8 i' [) T  E. `% X

首先我们来看最短路径dijkstra算法，他是寻找单源最短路径的。我们需要3个数组final[5],dist[5],path[5]。具体含义如下所示：其中最短路径长度是v0到该节点的最短路径

$ R  H# E# P1 K) i

首先，我们从v0开始，v0可以到v1与v4。我们先把他们的路径长度提案先到最短路径长度上，并修改前驱，前驱为v0。此时的v1与v4都没有找到最短路径，只有v0找到了到v0的最短距离，距离为0。在第一轮中循环遍历所有节点，找到没有确定最短路径且dist最小的顶点我们选取v4，说明找到了v0到v4的最短路径，(如果不是最短路径他只能走v1那条路线，但是他已经超过了5，走v1路线一定不是最短的)。

对其他final为false的节点进行更新，经过v4出去的节点有三个，将其全部更新，将v4到其他三个节点与v4记录中的最短路径相加，如果路径大于记录的路径长度则不用更新。最终更新结果如下图所示：

此时我们最短路径长度已经有两个确认了，寻找剩下的长度最小的V3，将v3的final改为true，对v1，v2的最短路径进行更新。其中v3指向的节点只有v2，v3的最短路径为7，7+6=13<14。将v2节点的最短路径更改为13，且前去改为v3

之后再次寻找最小长度，为v1，将v1的final改为true，从v1指出的阶段有v2，8+1=9<13.更新最后节点v2节点的最短路径，将其final改为true，更新其前驱为v1，结果如下：

可以观察到从v0到v1的最短距离为8，到v2的最短距离为9，v3为7，v4为5。那么如何寻找路径呢？已知到v2的长度为9，我们寻找他的前驱，前驱为1，v1的前驱为v4，v4的前驱为v0，我们就可以得到它的最短路径了，v0 ->v4 ->v1->v2。

由于图片上传有限制，图片都在附件中

7 o4 D" ^: h4 S, l1 A# J

旺旺碎冰冰

谢谢分享
- W; [5 h! d- U) h. K( L9 S8 |