前言

当然，我们想知道广州到上海用时最短的路径，用导航软件一搜就知道答案了。但博文本意是想通过中国地图理解Dijkstra算法的主要思想，所以会设立一些特殊条件使得读者更好的能根据求解广州到上海用时最短的路径从而学习Dijkstra算法的基本思路。

一、中国地图

提到中国地图，一句话便浮现在脑海里屹立在世界东方的雄鸡。我们都知道中国有23个省、5个自治区、4个直辖市、2个特别行政区。由于每个省份都有许多城市，地图使用每个省份具有代表的城市来求解问题。

二、广州到上海用时最短路径题目

1、题目详情

前言说到，设立一些特殊条件使得读者更好的能根据求解广州到上海用时最短的路径从而学习Dijkstra算法的基本思路，所以我们从广州到上海途中的路径，并非所有城市之间都能通过，且通过用时并非导航搜索出来的实际时间。

题目：
给出 i 条路径，输入城市A名称与城市B名称与其之间路径所需最短时间 T，求解从城市 S 到城市 E 的最短时间路径。
输入：
13
广州 香港 11
广州 福州 51
广州 长沙 46
香港 台北 83
福州 杭州 60
长沙 武汉 24
长沙 南昌 20
台北 上海 34
杭州 武汉 23
杭州 南京 23
南昌 合肥 15
上海 南京 27
合肥 南京 35

2、途中路径与时间分布

如果你是学习过图论算法，不难看出题目属于具有权重路径无向图求解最短路径的问题。所以不难看出，Dijkstra算法一般求解有权图中最短路径的问题。

从上面酷炫的地图中，我们可以简化成只有节点与路径的图。

3、逐步剖析Dijkstra算法

第一步：初始化数据表格

从图中图中可以看出，需要初始两个表格，一个用于存放仍未访问过的节点，一个用于存放从广州到该节点时间与上一个更新该节点数据的节点。

第二步：访问起点广州

由输入的数据可得，广州为本题目的起点，所以应首先访问广州节点，并在仍未访问节点列表将广州移除。

第三步：遍历与广州相邻所有节点并记录

在这里遍历先后顺序是没有关系的，我们先记录长沙与广州距离，右表中的长沙行的从从广州到该节点时间列应变为46，且上一更新数据节点改为广州，以此类推，福州与香港同理。遍历完成后，得到以下图表。

第四步：寻找从广州到该节点时间最小节点

此步骤将开始进入一个循环，因为后面的步骤会不断重复。我们寻找右表的从广州到该节点时间列里数值的最小值，不难看出，香港是该数值是最小的，因此进入香港节点进行遍历其相邻的城市。并将香港在仍未访问节点列表移除。

第五步：遍历与当前用时最短节点的相邻所有节点并记录

开始遍历香港相邻的城市。也就只有台北，且台北当前从广州到该节点时间是无穷大，所以记录到台北的节点时间应该为：香港的从广州到该节点时间 + 香港到台北所需要的时间 = 11 + 83 = 94。并将台北的上一更新数据节点更新为香港。

重复第四步：寻找从广州到该节点时间最小节点

到此为止，在表格内从广州到该节点时间最小且还在仍未访问节点列表内的节点为长沙，所以重复第五步，将遍历长沙的相邻可访问城市，并将长沙从仍未访问节点列表中移除。

重复第五步：遍历与当前用时最短节点的相邻所有节点并记录

开始遍历长沙相邻的城市。有南昌和武汉，根据第五步步骤，分别记录南昌与武汉的从广州到该节点时间与上一更新数据节点，得下图。

第六步：循环第四步与第五步，直至仍未访问节点列表为空

循环步骤不过多赘述，有特殊情况才会加以说明，循环步骤请看以下图示。

访问福州节点

访问南昌节点

访问武汉节点

可以看到，访问武汉节点时，需要遍历的相邻可访问节点是杭州，但是杭州已经被之前访问福州节点的时候记录过，从广州到该节点时间为111，所以我们要将从广州到武汉再到杭州的路线和当时在从广州到福州再到杭州的路线时间进行对比。

• 从广州到武汉再到杭州的路线通过时间：70 + 23 = 93
• 从广州到福州再到杭州的路线通过时间：111

经计算后，显然93 < 111，所以我们将原先表格中杭州的记录，覆盖为93并记录上一访问节点为武汉，下图所示。

访问杭州节点

访问台北节点

访问合肥节点

• 从广州到合肥再到南京的路线通过时间：101 + 15 = 116
• 从广州到杭州再到南京的路线通过时间：116

我们可以看到合肥或者杭州到南京所用的时间相同，所以我们可以将上一更新数据节点加入合肥节点。

访问南京节点

• 从广州到南京再到上海的路线通过时间：116 + 27 = 143
• 从广州到台北再到上海的路线通过时间：128

由于143 > 128，因此数据不发生变化，还是保持从广州到台北再到上海的路线为最优路线。

最后剩余一个上海节点

访问上海节点，遍历其相邻可访问的节点，但不难发现已经没有节点可以让它访问，所以放弃记录，直接从仍未访问节点列表移除上海。

最后一步：输出路径与所用最小时间

到此为止，我们已经将所有路径都遍历完即仍未访问节点列表为空，最后我们如果想输出最小路径，可以从上海开始，反推上一个更新数据节点，一直反推至广州，便是用时最短路径。
所以用时最短路径为：上海 <- 台北 <- 香港 <- 广州，最短用时为120。

三、Dijkstra算法总结

仔细的你可能已经发现，Dijkstra算法解出来的表格，实际上已经列出从出发点到各个节点的最小权重，回到我们解答题目的表格。可以看到，随便指定一个节点如南昌，可以直接得出从广州到该节点的最小时间为66，以及可以通过上一更新数据节点反推用时最小的路径：南昌 <- 长沙 <- 广州。

所以实际上，Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，解决的是带权有向图中单源最短路径（SSSP：Single-Source Shortest Path）的算法。

与贪心算法的关系

如果你完全理解了Dijkstra算法，其实它就是利用了贪心算法来实现的。如果你不知道什么是贪心算法，可以阅读我之前写的文章，你会对Dijkstra算法有更好的理解。
《人不能贪婪，但程序可以！用通俗的方法读懂贪心算法核心思想》

简述一下Dijkstra算法的流程就是：首先把起点到所有点的距离存下来找个最短的，然后从表格中找出距离最短的节点，且遍历与它相邻且还没被访问过的节点，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到各个点的最短距离。

使用Dijkstra算法求解广州到上海用时最短路径的python程序随后会上传到gitee。感兴趣的小伙伴可以关注我，随时知道我的动态哦。

图文均为原创，请尊重原创。
如果你觉得文章对你帮助，记得点赞关注一下哦。