Dijkstra(迪杰斯特拉)最短路径算法

Dijkstra(迪杰斯特拉)算法，是一种解决带权图中单源最短路径的经典算法。它由荷兰计算机科学家 Edsger Dijkstra 于1956年提出。在现实生活中，这个算法被广泛应用于导航系统、网络路由等场景。

比如在地图导航中，城市可以看作图中的节点，道路可以看作边，路程或时间可以看作权重。Dijkstra 算法可以帮助我们找到从起点城市到其他所有城市的最短路径。

Dijkstra 算法原理

Dijkstra 算法的核心思想是通过逐步扩展最短路径来找到从起点到所有其他节点的最短距离。它采用了一种贪心的策略，每次都选择当前未访问节点中距离最小的节点进行扩展。

算法维护两个关键的数据结构：一个记录最短距离的数组 dis，和一个记录已确定最短路径的顶点集合 T。初始时，将起点到自身的距离设为 0，到其他所有顶点的距离设为无穷大，集合 T 仅包含起点。

在每一轮迭代中，算法会从未确定最短路径的顶点中，选择当前 dis 数组中距离最小的顶点，将其加入集合 T。这个顶点的最短路径就此确定。接着，算法会以这个新加入的顶点为中转点，检查并更新从起点经过该顶点到达其他顶点的路径长度。如果通过这个中转点能得到一条更短的路径，就更新 dis 数组中对应顶点的距离值。

这个过程会不断重复，直到以下任一条件满足时算法结束：

1. 所有顶点都被加入到集合 T 中，表示所有可达顶点的最短路径都已确定；
2. 剩余未访问顶点的距离值都为无穷大，表示这些顶点从起点不可达。

当算法结束时，dis 数组中存储的就是从起点到所有其他顶点的最短距离，其中距离为无穷大的顶点表示从起点无法到达该顶点。同时，通过记录路径中的前驱节点，我们还可以重建出所有可达顶点的具体最短路径。

有点难理解？没事，下面结合可视化工具来理解这个过程。

可视化操作指南

本可视化工具比较强大，支持以下功能：

• 可以在左上角选择起始节点，这里默认是 A 节点，可以选择不同的开始节点，来看看不同起始节点的路径有什么不同；
• 双击连线可以修改边的权重，你可以修改权重，点击连线后，可以用 Del 键删除连线，或者点击节点后，可以用 Del 键删除节点。通过改变节点、连线、权重，来观察对最短路径的影响；
• 算法执行过程中，最短路径会用绿色线条高亮显示，右侧实时显示权重矩阵和每一步的计算过程；
• 支持一步步执行和自动执行，自动执行时，可以点击暂停按钮暂停执行；方便理解算法执行过程。

下面通过这个可视化工具，我们直观地理解 Dijkstra 算法是如何一步步找到最短路径的。当修改边的权重后，算法会重新计算，帮助我们理解不同权重对最短路径的影响。

具体查找最短路径过程

对于下面的无向图，我们选择 A 作为起始节点，来看看算法是如何一步步找到最短路径的。

点击下一步，第一步以 A 为起始点，记录了经过 A 到达各点的最短距离。

继续点击下一步，可以看到从上一步未访问的顶点中选择了距离最小的顶点，这里是距离为 4 的 D 顶点。

用 D 作为中转点，更新从 A 出发，经过 D 到达其他顶点的距离，如下图：

可以看到 B 和 E 的距离都更新了。 B 的距离从 10 更新为 6，E 的距离从无穷大更新为 4。

接着可以继续下一步，观察这里的搜索过程，看距离数字和已搜索顶点的变化过程。最后的结果如下：

Dijkstra 算法正确性证明

我们使用数学归纳法和反证法来证明 Dijkstra 算法的正确性。在算法执行到第 k 步时，已访问集合 T 中的每个节点 v 的距离 dist[v] 等于从起点到该节点的全局最短路径长度 short[v]。

归纳证明过程如下：

1. 归纳基础：k = 1 时，T 中只包含起点 s，dist[s] = short[s] = 0，因此命题在 k = 1 时成立。

2. 归纳假设：假设命题在第 k 步时成立，即 T 中所有节点的 dist 值都是最短路径长度。

3. 归纳步骤：证明第 k+1 步时命题也成立：

• 设第 k+1 步选择的节点为 v（v 是未访问节点中 dist 值最小的）；v 与集合 T 中的某个节点 u 相连；
• 需要证明：dist[v] = short[v]。

这里用反证法：

• 假设存在一条从起点 s 到 v 的路径 P，其长度是 short[v]，且 short[v] < dist[v]。
• 由于起点 s 在集合 T 中，而终点 v 不在集合 T 中，路径 P 必然至少经过一个集合 T 中的节点（除起点外）。因为起点 s 到任何不在 T 中节点的距离，都是通过 T 中的节点来计算和更新的。
• 设路径 P 上最后一个在集合 T 中的节点为 last，之后经过未访问集合中的节点 y 最终到达 v；下面看路径 P 的长度计算：

  short[v] = dist[last] + distance[last,y] + distance[y,v]  // 路径 P 的长度
           ≥ dist[y] + distance[y,v]                        // 根据 dist[y] 的更新规则
           ≥ dist[v]      

要理解下面这两个点才能明白上面的推导：

1. 首先由归纳假设，到达 last 的距离 dist[last] 是最短的；对于节点 y，根据 Dijkstra 算法的更新规则：dist[y] ≤ dist[last] + distance[last,y]
2. 又因为算法第 k+1 步选择了 v 作为当前最小距离节点，所以 dist[v] ≤ dist[y] + distance[y,v]。

于是就推导出 short[v] >= dist[v]，这和我们的假设 short[v] < dist[v] 矛盾，因此假设不成立，dist[v] 就是从起点到 v 的最短路径长度。这也证明了算法每一步选择的节点的距离都是最短路径长度。

Dijkstra 算法要求非负权重

最后再顺便提下，Dijkstra 算法要求图中所有边的权重都必须是非负数。这是因为：

1. 如果存在负权重边，算法的贪心策略可能会失效；
2. 一旦确定某个顶点的最短路径后，可能会通过负权重边找到更短的路径，这违背了算法的基本假设：已确定的最短路径不会再被更新。

比如下面的图，存在负权重边 CE 为 -13，到 E 点的最短路径其实如图红色箭头 1，但是算法计算出来的还是 10：

对于带负权边的图，需要使用其他算法（如 Bellman-Ford 算法）来解决最短路径问题。