前置定义

• arcs 邻接矩阵：arcs[i][j] 代表 i 到 j 的边长（此处把权值当成长度），两点不连通时用∞表示距离。

• V 是顶点集，S 是已确定最短路径的顶点集。

• final 数组标记顶点是否已加入 S，1 代表已找到最短路径，0 代表未确定。

• dist 数组存源点到当前点的最短距离，path 数组记录当前点的前驱顶点，最后靠它回溯完整路径。

步骤：

第一步：初始化参数

先把源点加入 S：

• final 数组：源点置 1，其余点置 0。

• dist 数组：源点置 0，邻接点置为对应边长，其余为∞。

• path 数组：全部置为 -1，-1 代表无前驱；如果源点 s 直接连通 k，path[k] 就等于 s。

第二步：选最短路径顶点

从 V-S（final 等于 0 的顶点）里，找到 dist 值最小的顶点记为 j，把 j 的 final 置为 1，代表这个点的最短路径已经确定。

第三步：松弛更新距离

遍历 j 的所有邻接顶点 k（写代码可直接遍历所有顶点），如果 dist[k] > dist[j] + arcs[j][k]，就更新 dist[k] 为 dist[j] + arcs[j][k]，同时把 path[k] 设为 j。

第四步：循环至结束

重复第二步和第三步，直到 S 包含所有顶点，也就是 final 数组全部为 1，此时 dist 数组就是源点到所有点的最短距离，path 数组可以回溯出完整路径。

总结

Dijkstra 算法的核心就是“选最短点、更新邻接距离”的循环，不用死记硬背。现在你可以拿出自己的笔记，对着步骤走一遍示例图的推导，马上就能吃透逻辑。