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 到达各点的最短距离。

![Dijkstra 算法第一步](https://slefboot-1251736664.file.myqcloud.com/20241122_ai_gallery_dijkstra_step1.png)

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

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

![Dijkstra 算法第二步](https://slefboot-1251736664.file.myqcloud.com/20241122_ai_gallery_dijkstra_step2.png)

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

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

![Dijkstra 算法最终结果](https://slefboot-1251736664.file.myqcloud.com/20241122_ai_gallery_dijkstra_step_final.png)

## 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：

![Dijkstra 算法负权重图](https://slefboot-1251736664.file.myqcloud.com/20241205_ai_gallery_dijkstra_negative_weight.png)

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