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。

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