29 最短路径：迪杰斯特拉（Dijkstra）算法与选择最节省时间的行走路线问题
你好，我是王健伟。
前面我们讲解了用普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法来寻找连通图的最小生成树，从而解决诸如如何修路费用最少这样的问题。这次我和你分享图的第二个实际用途——最短路径。那么，什么是最短路径呢？
最短路径
在带权图中，最短路径指的是图中两个顶点之间经过的边上权值之和最小的路径。如下图所示：
在图1中，顶点A到E之间的路径有多条，这里我举几个例子。
- A→B→E，顶点A到E的边上权值之和为122。
- A→D→C→E，顶点A到E的边上权值之和为66。
- A→D→B→E，顶点A到E的边上权值之和为116。
- A→D→C→B→E，顶点A到E的边上权值之和为176。
- A→D→C→F→E，顶点A到E的边上权值之和为71。
可以看到，A→D→C→E所代表的的路径就是最短路径，权值之和为66。那么对于一个带权有向图，给定一个顶点，如何求得该顶点到其余各个顶点的最短路径呢？其实这个问题也适用于带权无向图，因为带权无向图中的每条边就相当于带权有向图方向相反的两条边。
如果采用带权的邻接矩阵作为图1中有向图的存储结构，则结果如图2所示：
迪杰斯特拉（Dijkstra）算法详解
荷兰籍的一位计算机科学家、计算机先驱之一迪杰斯特拉提出了一个按路径长度递增的次序产生最短路径的算法，称为迪杰斯特拉算法。以图1为例，我们看一看该算法的实现思路。
- 设置一个集合S用于存放已经找到最短路径的顶点，该集合开始时只包含给定的第一个顶点。这个顶点也叫源顶点/起始顶点。我们就是要从该顶点找到其余各个顶点的最短路径。这里先把顶点A保存进去，这预示着从源顶点A开始已经找到了到目标顶点A的最短路径，毕竟本来这两个点就是同一个点。
S = {A}
设置一个叫dist的数组，元素数量等同于图中顶点数量。该数组用于存放当前起始点到其他各个顶点的最短距离（权值最小），开始时该数组的内容就是图2中源顶点A所在行的值，即{0,22,∞,6,∞,∞}，因为这组数据正好代表源顶点A到其他各个顶点的距离。
设置一个叫path的数组，元素数量等同于图中的顶点数量。该数组用于记录每个顶点在最短路径上的前趋节点，里面的内容需要根据dist中的内容得出， dist中对应下标位置是0或∞，则path对应位置是-1。如果dist中对应下标位置有权值，那么path对应位置是源顶点的下标，所以开始时该数组内容为{-1,0,-1,0,-1,-1}。
- 开始计算从源顶点A到不在集合S中的顶点的最短路径。
A→B : 距离=22
A→C : 距离=∞ （∞表示A到C之间不直接相连）
A→D : 距离=6
A→E : 距离=∞
A→F : 距离=∞
现在，得到了从顶点A到其他所有顶点的路径长度。我们从其中选出一条最短的路径，即：
A→D : 距离=6
并把顶点D也放入到集合S中，表示源顶点A到顶点D的最短路径已找到，如图3：
S = {A，D}
- 在增加了D顶点到集合后，顶点A（经过顶点D）到其他所有顶点是不是有更短的路径存在呢？
这主要得看顶点D到达哪些顶点，根据图2，顶点D对应的行数字是{∞,10,20,0,∞,∞}，这表示顶点D可以到达顶点B、C。注意这里要求顶点D到达的目标顶点必须不能包含在集合S中，所以看一下顶点A通过顶点D到达顶点B和到达顶点C的距离：
A→B : 距离=(6+10)=16（通过A→D→B路径）
A→C : 距离=(6+20)=26（通过A→D→C路径）
因为原来的顶点A到达顶点B和顶点C的距离是保存在dist数组的，dist数组当前内容为{0,22,∞,6,∞,∞}。可以看到，原来A→B的距离是22，A→C的距离是∞，而现在A→B和A→C的距离明显变得更小了，所以我们要更新dist数组中源顶点A到达顶点B和顶点C的距离，来保证dist数组中始终保存着源顶点A到其他各个顶点的最短距离。更新后dist数组的内容为{0,16,26,6,∞,∞}，这表示下面两个情况。
- 源顶点A到达顶点B的最短距离为16。
- 源顶点A到达顶点C的最短距离为26。
因为上述找最短路径找到了D顶点（下标3），dist数组中有两个位置做了修改，path数组也要在相应位置做修改，即path数组中的内容也从原来的{-1,0,-1,0,-1,-1}更新为{-1,3,3,0,-1,-1}，这表示什么呢？
- 源顶点A到达顶点B是通过顶点D到达的（B的上一个顶点是D）。
- 源顶点A到达顶点C也是通过顶点D到达的（C的上一个顶点是D）。
- 整理一下源顶点到其他顶点的距离信息：
A→B : 距离=16（通过A→D→B路径）
A→C : 距离=26（通过A→D→C路径）
A→D : 距离=6
A→E : 距离=∞
A→F : 距离=∞
因为顶点D已经在集合S中了，所以A→D这条路径就不考虑了，从其余的4条路径中选出一条最短的路径，注意，这4条路径的弧头顶点还没有找到从源顶点A到它们的最短路径。所以：
A→B : 距离=16（通过A→D→B路径）
并把顶点B也放入到集合S中，表示源顶点A到顶点B的最短路径已找到，如图4：
S = {A，D，B}
- 在增加了B顶点到集合后，顶点A（经过顶点B）到其他所有顶点是不是有更短的路径存在呢？
这主要得看顶点B到达哪些顶点。根据图2，顶点B对应的行数字是{∞,0,∞,∞,100,∞}，这表示顶点B可以到达顶点E。注意这里要求顶点B到达的目标顶点必须不能包含在集合S中。所以看一下顶点A通过顶点B到达顶点E的距离：
A→E : 距离=(6+10+100)=116（通过A→D→B→E路径）
dist数组当前内容为{0,16,26,6,∞,∞}，更新后dist数组的内容为{0,16,26,6,116,∞}，path数组当前的内容为{-1,3,3,0,-1,-1}，更新后path数组的内容为{-1,3,3,0,1,-1}。
- 整理一下源顶点到其他顶点的距离信息：
A→B : 距离=16（通过A→D→B路径）
A→C : 距离=26（通过A→D→C路径）
A→D : 距离=6
A→E : 距离=116（通过A→D→B→E路径）
A→F : 距离=∞
因为顶点D、B已经在集合S中了，所以A→D、A→B这两条路径就不考虑了，从其余的3条路径中选出一条最短的路径，即：
A→C : 距离=26（通过A→D→C路径）
并把顶点C也放入到集合S中，表示源顶点A到顶点C的最短路径已找到，如图5：
S = {A，D，B，C}
- 在增加了C顶点到集合后，顶点A（经过顶点C）到其他所有顶点是不是有更短的路径存在呢？
这主要得看顶点C到达哪些顶点，根据图2，顶点C对应的行数字是{∞,50,0,∞,40,10}，这表示顶点C可以到达顶点B、E、F。注意这里要求顶点C到达的目标顶点必须不能包含在集合S中，所以只需要看一下顶点A通过顶点C到达顶点E、F的距离：
A→E : 距离=(6+20+40)=66（通过A→D→C→E路径）
A→F: 距离=(6+20+10)=36（通过A→D→C→F路径）
dist数组当前内容为{0,16,26,6,116,∞}，更新后dist数组的内容为{0,16,26,6,66,36}，path数组当前的内容为{-1,3,3,0,-1,-1}，更新后path数组的内容为{-1,3,3,0,2,2}。
- 整理一下源顶点到其他顶点的距离信息：
A→B : 距离=16（通过A→D→B路径）
A→C : 距离=26（通过A→D→C路径）
A→D : 距离=6
A→E : 距离=66（通过A→D→C→E路径）
A→F : 距离=36（通过A→D→C→F路径）
因为顶点D、B、C已经在集合S中了，所以A→D、A→B、A→C这3条路径就不考虑了，从其余的2条路径中选出一条最短的路径，即：
A→F : 距离=36（通过A→D→C→F路径）
并把顶点F也放入到集合S中，表示源顶点A到顶点F的最短路径已找到，如图6：
S = {A，D，B，C，F}
- 在增加了F顶点到集合后，顶点A（经过顶点F）到其他所有顶点是不是有更短的路径存在呢？
这主要得看顶点F到达哪些顶点，根据图2，顶点F对应的行数字是{∞,∞,∞,65,35,∞}，这表示顶点F可以到达顶点D、E。注意这里要求顶点F到达的目标顶点必须不能包含在集合S中，所以只需要看一下顶点A通过顶点F到达顶点E的距离：
A→E : 距离=(6+20+10+35)=71（通过A→D→C→F→E路径）
这个距离比原来A→E的距离更远，所以忽略。
dist数组维持当前内容{0,16,26,6,66,36}，path数组维持当前内容{-1,3,3,0,2,2}。
- 整理一下源顶点到其他顶点的距离信息：
A→B : 距离=16（通过A→D→B路径）
A→C : 距离=26（通过A→D→C路径）
A→D : 距离=6
A→E : 距离=66（通过A→D→C→E路径）
A→F : 距离=36（通过A→D→C→F路径）
因为顶点D、B、C、F已经在集合S中了，所以A→D、A→B、A→C、A→F这4条路径就不考虑了，只剩下也只能选择如下路径，即：
A→E : 距离=66（通过A→D→C→E路径）
并把顶点E也放入到集合S中，表示源顶点A到顶点E的最短路径已找到，如图7：
S = {A，D，B，C，F，E}
- 在增加了E顶点到集合后，顶点A（经过顶点E）到其他所有顶点是不是有更短的路径存在呢？ 没有。因为顶点E没有到达任何其他顶点。
至此，集合S中已经包含了图中的所有顶点，迪杰斯特拉算法结束。此时：
dist数组内容为：{0,16,26,6,66,36}
path数组内容为：{-1,3,3,0,2,2}
通过上面两个数组的内容，就可以分析出从源顶点A到其他顶点的最短路径。那么我们来看两个更具体的问题。
- 如何得到从源顶点A到顶点B的最短路径长度？
第一就是查找dist数组，查找下标为1（顶点B）的元素值，发现是16，这意味着从顶点A到顶点B的最短路径长度是16。第二就是看path数组以获得从顶点A到顶点B的最短路径“path[1] = 3；path[3]=0；”，因为0代表顶点A即源顶点，找到源顶点之后，就可以得到结果了，以反序将刚刚path数组的结果输出就是最短路径，即0→3，这些数字代表顶点的下标，所以，顶点A到B的最短路径如图8所示：
- 如何查找从源顶点A到顶点E的最短路径长度？
第一就是查找dist数组，查找下标为4（顶点E）的元素值，发现是66，这意味着从顶点A到顶点E的最短路径长度是66。第二就是看path数组以获得从顶点A到顶点E的最短路径“path[4] = 2；path[2] = 3；path[3] = 0”，因为0代表顶点A即源顶点，找到源顶点之后，就可以得到结果了，以反序将刚刚path数组的结果输出就是最短路径，即0→3→2，这些数字代表顶点的下标，所以，顶点A到E的最短路径如图9所示：
想一想，为什么通过查找path数组就可以找到最短路径呢？这是因为在每次更改dist数组后都会在path数组中记录当前顶点的上一个顶点是谁。所以利用倒推的方式就可以把路径推导出来。
完整的实现迪杰斯特拉（Dijkstra）算法的类模板相关源码，参见课件中GraphMatrix类模板的定义与实现。这里我们重点看其中的ShortestPath_Dijkstra()成员函数的实现代码。
main主函数中代码如下：
GraphMatrix<char> gm;
gm.InsertVertex('A');
gm.InsertVertex('B');
gm.InsertVertex('C');
gm.InsertVertex('D');
gm.InsertVertex('E');
gm.InsertVertex('F');
//向图中插入边
gm.InsertEdge('A', 'B', 22); //22代表边的权值
gm.InsertEdge('A', 'D', 6);
gm.InsertEdge('B', 'E', 100);
gm.InsertEdge('C', 'B', 50);
gm.InsertEdge('C', 'E', 40);
gm.InsertEdge('C', 'F', 10);
gm.InsertEdge('D', 'B', 10);
gm.InsertEdge('D', 'C', 20);
gm.InsertEdge('F', 'D', 65);
gm.InsertEdge('F', 'E', 35);
//显示图形
gm.DispGraph();
gm.ShortestPath_Dijkstra('A');
执行结果如下：
从上述代码不难看到，迪杰斯特拉算法实现中使用的dist数组和前面讲过的普里姆算法中使用的lowcost数据非常类似。在实现代码中，采用了带权的邻接矩阵作为图的存储结构，算法中使用了双重循环，每重循环的循环次数都不会超过顶点数量，所以该算法的时间复杂度为O($|V|^{2}$)。
迪杰斯特拉算法解决了从某个源顶点到图中其余各顶点的最短路径问题。可能你会问了，是否能够找到图中某个顶点开始到另一个特定顶点的最短路径？
其实这样做和求某个顶点开始到其他所有顶点最短路径并没有区别，依然要采用迪杰斯特拉算法不断计算从开始顶点到其他各个顶点的最短距离，所以时间复杂度仍旧是O($|V|^{2}$)。所以，即便是寻找某两个点之间的最短路径，解决办法仍旧是选择其中一个作为源顶点，然后用迪杰斯特拉算法求出到其余顶点的最短路径，这些路径中肯定包含着到另外一个顶点的最短路径，除非这两个顶点之间不可达。
图的最短路径求解问题在实际生活中有非常实用的价值，应用广泛。比如城市公交或者城市地铁站都可以看作是一张图，其中的各个站点都可以看作是图中顶点。如果把全国交通图看成是一张图的话，那么各个城市就可以看作是图中的顶点。如图10所示：
在图10中，从一个城市到达另外一个城市有多种走法。
- 如果把城市之间的距离作为权值，利用最短路径算法，可以找到从某个城市去到另外一个城市如何走距离最短。
- 如果把城市之间驱车所花费的时间作为权值，利用最短路径算法，可以找到从某个城市到另外一个城市如何走最节省时间。
- 如果把城市之间坐车所花费的金钱作为权值，利用最短路径算法，可以求解出如何乘车花费的金钱最少。
小结
这节课我给出一个图来向你详细阐述最短路径的概念，然后提出了如何从某个顶点求得到其他各个顶点的最短路径的问题。从而引出了迪杰斯特拉（Dijkstra）算法——专门用来求从某个顶点到其他各个顶点最短路径的算法。
本节我用大量的篇幅阐述了迪杰斯特拉算法的详细实现过程，我们首先设置集合S来存放已经找到最短路径的顶点、设置dist数组存放当前起始点到其他各个顶点的最短距离、设置path数组记录每个顶点在最短路径上的前趋节点。然后阐述详细的算法步骤。
充分理解这些算法的实现步骤是后序能够写出迪杰斯特拉算法代码的根本，否则即便是阅读别人实现的迪杰斯特拉算法，也会一头雾水。接着，我带你完成了整个迪杰斯特拉算法的实现代码。
迪杰斯特拉算法解决了从某个源顶点到其余各顶点的最短路径问题，在实际生活中有非常实用的价值，比如我为你举的几个例子，分别是从某个城市到另一个城市如何走距离最短、如何走最节省时间、如何乘车花费的金钱最少等。你可以举一反三，仔细想想还有哪些实际生活中的问题可以用迪杰斯特拉算法解决呢？
课后思考
许多城市的地铁线路非常繁杂，以深圳为例，如图11所示：
目前深圳地铁已经开通运营了10几条线路。对于一些行动不便的老人或者残障人士，乘坐地铁时，如果目的地特别远并且要换乘多次地铁才能达到，则经常希望换乘的次数尽可能少。怎样做到呢？
- Yj.yolo 👍（0） 💬（0）
【课后思考题】如果希望换乘次数很少，则应该考虑的是节点个数，即将①起始站②可换乘的站③终点站 当作图中的节点，然后考虑起始站到终点站的路径中，节点数更少的路径。将迪杰斯特拉算法中的“距离数组”换成“经过的节点数数组”，同理，按照迪杰斯特拉最短距离比较思想，去维护“节点数组”中的数值。
2023-07-13