Dijkstra 单源最短路径算法动画

从源点出发，反复选择当前距离最小且尚未确定的点，再用它的相邻边更新其它点距离。适用于边权非负的图。

控制

慢 快
当前步： 0 / 0
当前点： -
本步结果： 初始化

当前判断

dist[v] = min(dist[v], dist[u] + w(u, v))

源点 0 的距离设为 0，其它点暂时记为 ∞。

图与距离表

源点 0
无向带权图 边权均为非负数
4 8 8 11 7 2 4 9 14 10 2 1 6 7 0 1 2 3 4 5 6 7 8
源点 当前点 正在松弛的邻点 已确定最短路
距离表 初始化

讲解要点

  • dist 数组：记录从源点到每个点的当前最短估计值。
  • 确定点：每轮选出未确定点里 dist 最小的点，它的最短路就固定下来。
  • 松弛操作：若 dist[u] + w(u,v) 更小，就更新 dist[v] 和前驱。
  • 使用条件：Dijkstra 要求边权非负；有负权边时这个“当前最小即可确定”的判断会失效。
  • 复杂度：本页代码写法为 O(n^2 + m)，适合讲解和中小规模图。

C++ 核心代码

const int INF = 0x3f3f3f3f;
vector<int> dist(n + 1, INF), pre(n + 1, -1);
vector<bool> used(n + 1, false);

dist[s] = 0;

for (int step = 1; step <= n; step++) {
    int u = -1;
    for (int i = 1; i <= n; i++) {
        if (!used[i] && (u == -1 || dist[i] < dist[u])) {
            u = i;
        }
    }
    if (u == -1 || dist[u] == INF) break;

    used[u] = true;
    for (auto edge : graph[u]) {
        int v = edge.to;
        int w = edge.w;
        if (!used[v] && dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pre[v] = u;
        }
    }
}