Dijkstra算法求最短路径

一.  前言

当我们给定一个有向带权图D与一个点v的时候，点v到D其他顶点的路径可能有多条，那么如何求出点v到D中其他各顶点的最短路径呢？可以用Dijkstra算法解决

二.  Dijkstra算法

1.  Dijkstra算法是按照路径长度的递增次序，逐步产生最短路径的算法

这个算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时，原点 s 的路径权重被赋为 0 （d[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把d[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于所有顶点的集合 V 中的任意顶点 v， 若 v 不为 s 和上述 m 之一， d[v] = ∞）。当算法结束时，d[v] 中存储的便是从 s 到 v 的最短路径，或者如果路径不存在的话是无穷大。

2.  边的拓展是Dijkstra 算法的基础操作：如果存在一条从 u 到 v 的边，那么从 s 到 v 的最短路径可以通过将边（u, v）添加到尾部来拓展一条从 s 到 v 的路径。这条路径的长度是 d[u] + w(u, v)。如果这个值比目前已知的 d[v] 的值要小，我们可以用新值来替代当前 d[v] 中的值。拓展边的操作一直运行到所有的 d[v] 都代表从 s 到 v 的最短路径的长度值。此算法的组织令 d[u] 达到其最终值时，每条边（u, v）都只被拓展一次。

3.  算法维护两个顶点集合 S 和 Q。集合 S 保留所有已知最小 d[v] 值的顶点 v ，而集合 Q 则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 d[u] 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中，算法对 u 的每条外接边 (u, v) 进行拓展。

三.  举例

以下图为例：

我们可以构建数组，来更好的分析Dijkstra算法：

最短路径就是起始顶点到该节点的最短路径长度（权值）

上一个顶点就是起始顶点到该顶点的最短路径的前一个顶点，如果没有设置为-1

设顶点被使用状态为1，未被使用状态为0

1.  首先从顶点0开始：

0到自身权值为0，同时顶点0为起始顶点，所以将0顶点的上一个顶点设为-1

0顶点到1的权值为10，同时，顶点1的上一个顶点设置为0

0顶点到2的权值没有直达边，所以用无穷表示，同时，顶点2的上一个顶点设置为-1

0顶点到3的权值为30，同时，顶点3的上一个顶点设置为0

0顶点到4的权值为100，同时，顶点4的上一个顶点设置为0

使用完顶点0，将顶点0是否被使用设置为1，如下图：

2.  顶点0已经被使用，接下来从未被使用的顶点中选取从顶点0到该顶点权值最小的顶点1开始，1到2的权值为50，而0可以从1到2，则0到2这条路径的权值为10 + 50 = 60，60 < 无穷，所以将2的最短路径更新为60，同时顶点2上一个顶点更新为1，使用完1顶点，更新使用状态为1

3.  接下来，从未被使用的顶点有2,3,4，其中0到3的权值最小，为30，而3到2的权值是20，而0可以从3到2，则0到2这条路径的权值为30 + 20 = 50， 50 < 60，将顶点2的最短路径更新为50，同时上一个顶点更新为3

4.  顶点3还可以到4，到4为权值为60，而0可以从3到4，则0到4这条路径的权值为30 + 60 = 90， 90 < 100， 则将顶点4的最短路径更新为90，同时上一个顶点更新为3，顶点3使用完毕，更新使用状态为1

5.  接下来，从未被使用的顶点有2,4，其中0到2的权值最小，为30，2到4权值为10，而0可以从3到2再到4，则这条路径的权值为：30 + 20 + 10 = 60 , 60 < 90 ，则将顶点4的最短路径更新为60，同时上一个顶点更新为2，顶点2使用完毕，更新使用状态为1

6.  还剩最后一个顶点4，但是顶点4出度为0，算法完成，则

0到1最短路径：10

0到2最短路径：50

0到3最短路径：30

0到4最短路径：60

7.  我们知道了起始顶点到每一个顶点的最短距离，那么如何根据上面的数组，将起始顶点到每个顶点的最短距离的路径还原出来呢？以顶点4为例，步骤如下：

通过上图我们可以看出，顶点4的上一个顶点为2，顶点2的上一个顶点为3，顶点3的上一个顶点为0，则

0到4的最短路径为：0 —> 3 —> 2 —> 4，依次类推

0到3的最短路径为：0 —> 3

0到2的最短路径为：0 —> 3 —> 2

0到1的最短路径为：0 —> 1

四.  参考资料

《数据结构》殷人昆版

维基百科戴克斯特拉算法