Dijkstra 最短路径

Dijkstra 解决带权图上的单源最短路径——边有”成本”，要找从起点到终点总成本最小的路径。BFS 是 Dijkstra 在”所有边权重 = 1”时的特例。

核心思想：贪心 + 松弛

不变量：每次取出”当前距离最短的未访问节点”，它的距离就是最终最短距离——因为任何绕路都需要先经过另一个未访问节点，而那个节点的距离不会更小。

每次从未访问集合里取出最近的节点 u，做两件事：

1. 把它永久标记为已访问
2. 用它去松弛所有邻居：如果 dist[u] + weight(u, v) < dist[v]，就更新 dist[v]

和 BFS 的关系

如果你已经看过 优先队列，会理解为什么 Dijkstra 需要堆——每次找”当前最近的未访问节点”就是 extractMin。我们这里图小，用线性扫描代替堆，逻辑等价。

复杂度

• 时间：O(E log V)（用堆）或 O(V²)（用线性扫描，本实现）
• 空间：O(V)

重要前提

所有边权必须非负。负权会破坏”取最近就锁定”的不变量。负权图要用 Bellman-Ford。

在动画里看什么

• 每个节点下方的数字 = 当前暂时距离（从起点出发的已知最短路径长度，∞ 表示尚未触达）
• 深蓝实心 + 脉冲 = 正在处理的节点 u
• 浅蓝 = 正在被松弛的邻居 v
• 颜色渐变 = 已访问节点的访问顺序（冷 → 暖）
• 暖红粗线 = 最终回溯出的最短路径

最值得看的地方：A → C → B 这条 “2 + 1 = 3” 的迂回，比 A → B 直接的 “4” 更短——Dijkstra 会自动发现这种绕远反而更近的情况。