小序
最近在看《算法图解》这本书，对【狄克斯特拉算法】这一章颇有感触。
狄克斯特拉算法是非常著名的算法，是改变世界的十大算法之一，用于解决【赋权】【有向无环图】的【单源最短路径】问题。
如果没有这种算法，因特网肯定没有现在的高效率。只要能以“图”模型表示的问题，都能用这个算法找到“图”中两个节点间的最短距离。狄克斯特拉算法的稳定性至今仍无法被取代。
注：狄克斯特拉算法的原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径，产生一个最短路径树（树是没有环的图）。本文讨论的是后者。
定义
如果觉着序言中加红标粗的这句释义难理解？让咱一一拆解，您就明白了。倘若知晓概念，可选跳过此节。
何为图
- 图由【节点】和【边】组成，用来模拟不同东西的连接关系。
图 1-1
我们发现我们太多的现实场景都与图这种结构相关。人与人之间的关联，地点与地点之
间的关联，各类拓扑图等。后文会例举具体场景案例。
何为有向无环图
何为有向？
图 1-1 是无向图，而图 1-2 则是有向图，区别在于后者标注了点与点之间关联方向。
图 1-2
何为无环？
如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图。
- Q&A Q：图 1-2 是有向无环的吗？
A：不是，因为 A 经过 C 之后又回到了 A。
图 1-3
那图 1-3 是有向无环的吗？
答：是的，欲知更多在 zh.wikipedia.org/wiki/有向无环图。
何为赋权
这里的“权”即“权重”，“赋权”即是给图的边赋权重值。
图 1-4
比如图 1-4 从点 1 到点 2，需要走 10 步，从点 1 到点 5 需要 100 步，这里的 10 和 100 即为“权重值”。
特注：Dijkstra 算法边权非负。
何为单源最短路径
最短路径是计算给定的两个节点之间最短（最小权重）的路径，如果起点确定，则叫单源最短路径。
最短路径有很多现实应用：很多地图均提供了导航功能，它们就使用了最短路径算法或其变种。我们在很多社交平台上查看某人的简介时，平台会展示你们之间有多少共同好友，并列出之间的关系，也是基于此算法。
我们现在在回看这句定义：
狄克斯特拉算法用于解决【赋权】【有向无环图】的【单源最短路径】问题。
您是否明了？只需紧扣“赋权”、“有向无环图”、“单源最短路径”这三个关键词。粗犷点讲，这个算法就是用于找两点之间的最短距离的。
实现
那么重点来了，狄克斯特拉算法到底是怎样实现的呢？
回到《算法图解》一书，我们可以看到最直观的例子。
图 2-1
在图 2-1 中，从起点到终点的最短路径是多少呢？
如果您使用广度优先搜索（BFS），得到的答案将是 7（具体实现，按下不表），但这明显不是最优解。我们可以人眼识别，看出正确答案应该是 6，即从起点 —— 到 B 点 —— 到 A 点 —— 到终点。
如果通过计算机，正确答案是怎么算出来的呢？正是咱们的主角——狄克斯特拉算法。
四步走
狄克斯特拉算法包括 4 个步骤：
- 找出“最便宜”的节点，即可在最短时间内到达的节点。
- 更新该节点的邻居的开销，其含义将稍后介绍。
- 重复这个过程，直到对图中的每个节点都这样做了。
- 计算最终路径。
- 第一步：找出“最便宜”节点
咱先看第一步，你起点，有两条路可选，去到 A 需 6 步，去到 B 需 2 步，先不管其它节点，B 点即最便宜节点 记录以下集合，这点非常重要。
图 2-2
图 2-3
- 第二步：计算经过节点 B 前往各个邻居所需时间。
起点经过 B 点 到 A 需 5 步，起点经过 B 点 到终点需 7 步，之前的集合中起点到 A 点需要 6 步，到终点是正无穷，现在有了更优解，则需要更新该开销集合，得出图 2-4。
图 2-3
图 2-4
- 第三步：重复！！！
如何重复？我们已经基于 B 点做了更新操作，我们需要对剩下节点做类似的操作。图 2-4 表中，除了 B ，A 点的开销最小，所以我们需要对 A 点开刀了。—— “更新节点 A 所有邻居的开销。”
起点经过 A 点到终点需要 1 步，5 + 1 = 6 ，小于图 2-4 中终点开销所需值 7，我们应该更新开销集合。
图 2-5
我们对每个节点都采用了狄克斯特拉算法（无需对终点这样做），所以图 2-5 是最后的开销集合，也是最终最优解。从起点到终点最少只需 6 步！
- 第四步？
细心的朋友可能发现了，说好的四步呢？上面怎么只有三步？这里作者在留了个“心机”，其实上面的例子只是算出了最小的开销的值，并未得出实现最小开销的最终路径，即缺少了一个回溯的过程。
如何计算最终路径？作者这里又举了一个例子，且此例要更为复杂一些。不过本瓜认为：狄克斯特拉算法的核心在于第二步、第三步（开销数组的更新），第四步得出具体路径只是增加一个父子关系进行回溯补充。
图 2-6
如图 2-6 ，问：从乐谱到钢琴的最短路径是多少？
答案是： 乐谱 —— 唱片 —— 架子鼓 —— 钢琴，你知道其中开销集合的具体更新过程吗？我想有人面试应该遇到过这题。了解更多
本瓜简述：由点【乐谱】出发，相邻【唱片】和【海报】两点，将它们放到开销数组中，值分别为 0 和 5。0 小于 5，所以基于【海报】，执行第二步，拿到【乐谱】通过【海报】达到其相邻的点的值，分别是【吉他】30 和【架子鼓】35，此时开销数组里面有四个值：
| 名称 | 开销 |
| 海报 | 0（已遍历相邻值） |
| 唱片 | 5 |
| 吉他 | 30 |
| 架子鼓 | 35 |
| ... | ... |
5<30<35，进行重复操作，以【唱片】为基础，拿到【乐谱】到它相邻的点的值。分别为【吉他】20，【架子鼓】25，都小于开销数组中的值，进行更新。此时的开销数组为：
| 名称 | 开销 |
| 海报 | 0（已遍历相邻值） |
| 唱片 | 5（已遍历相邻值） |
| 吉他 | 20 |
| 架子鼓 | 25 |
| ... | ... |
继续遍历，20 < 25，此时应该基于【吉他】，【吉他】与钢琴相连，【乐谱】通过【唱片】到【吉他】再到【钢琴】，需 40，更新数组。25 < 40，再基于【架子鼓】遍历，架子鼓也只和【钢琴】相连，【乐谱】——【唱片】——【架子鼓】——【钢琴】，值为 35，35 小于 40 ，更新。最终只有【钢琴】这一点没遍历，而【钢琴】又是终点，则执行结束啦。最终是：
| 名称 | 开销 |
| 海报 | 0（已遍历相邻值） |
| 唱片 | 5（已遍历相邻值） |
| 吉他 | 20（已遍历相邻值） |
| 架子鼓 | 25（已遍历相邻值） |
| 钢琴 | 35（终点，无需遍历） |
能轻松过一遍，算法思想就没啥问题啦~
其实，最短路径不一定是物理距离，也可以转化其它度量指标，比如钱、时间等等。将生活中的场景抽象成此类算法问题，妈妈再也不用担心我走弯路了~
狄克斯特拉！牛！
致敬此算法的作者 —— Edsger Wybe Dijkstra，他在1972年获得图灵奖。
代码
算法思想很重要，但 TALK IS CHEAP!! 这里用 py 实现。同时也找到一篇 JS 实现-Finding the Shortest Path in Javascript: Dijkstra’s Algorithm 挖个坑，有空翻译。/(ㄒoㄒ)/~~
node = find_lowest_cost_node(costs) // 在未处理的节点中找出开销最小的节点 while node is not None: // 这个while循环在所有节点都被处理过后结束 cost = costs[node] neighbors = graph[node] for n in neighbors.keys(): // 遍历当前节点的所有邻居 new_cost = cost + neighbors[n] if costs[n] > new_cost: // 如果经当前节点前往该邻居更近， costs[n] = new_cost // 就更新该邻居的开销 parents[n] = node // 同时将该邻居的父节点设置为当前节点 processed.append(node) // 将当前节点标记为处理过 node = find_lowest_cost_node(costs) // 找出接下来要处理的节点，并循环 // 找出开销最低的节点 def find_lowest_cost_node(costs): lowest_cost = float("inf") lowest_cost_node = None for node in costs: // 遍历所有的节点 cost = costs[node] if cost < lowest_cost and node not in processed:// 如果当前节点的开销更低且未处理过， lowest_cost = cost // 就将其视为开销最低的节点 lowest_cost_node = node return lowest_cost_node
costs 数组即为开销数组，可以得到最小开销，也就是最短路径。
有兴趣也可看北大屈婉玲教授的视频——《单源最短路径问题及算法》，讲的非常清晰。
迷思
美丽心灵
狄克斯特拉算法实际上是一个贪婪算法。因为该算法总是试图优先访问每一步循环中距离起始点最近的下一个结点。
本瓜正好最近在看一部电影——《美丽心灵》，又加深了对“纳什均衡”的认知。
在博弈论中，纳什均衡（英语：Nash equilibrium，或称纳什均衡点）是指在包含两个或以上参与者的非合作博弈（Non-cooperative game）中，假设每个参与者都知道其他参与者的均衡策略的情况下，没有参与者可以透过改变自身策略使自身受益时的一个概念解。—— 维基百科
在一个博弈过程中，无论对方的策略选择如何，当事人一方都会选择某个确定的策略，则该策略被称作支配性策略。如果任意一位参与者在其他所有参与者的策略确定的情况下，其选择的策略是最优的，那么这个组合就被定义为纳什平衡。—— 百度百科
二者综合，本瓜产生了困惑：
在这个狄克斯特拉算法中，我们每走一步都是一次博弈。如果将每一步的博弈交给不同的人去做，都达到自身的最优解，那么最终的解是否一定是最优的呢......？这涉及算法的稳定性？还是概念混淆了，还是有点哲学那味了？Anyway, 这东西还挺有意思的。算法、博弈论、最优解......
概念整理
- 图算法
“在我所知道的算法中，图算法应该是最有用的”。—— Aditya Bhargava（《算法图解》作者）
图算法有三类核心：路径搜索、中心性计算、社群发现。
图算法还有最基础的两个遍历算法：
- 广度优先搜索（BFS）
- 深度优先搜索（DFS）
学过《数据结构》的应该都不陌生。同时，BFS 可以拿出与狄克斯特拉算法做对比，前者可用于在非加权图中查找最短路径，后者用于加权图中。还要提一嘴的是，如果图的权为负数，要使用【贝尔曼-福德算法】。有兴趣再拓展⑧。
工具
- Dijkstra's Algorithm Solver（绘制）：mdahshan.github.io/dijkstra/
以上
撰文不易，还需鼓励。年轻人，讲点武德 ~ 喜欢就点赞，反感就三连。谢谢~
我是掘金安东尼，一位持续输出的个人站长~
