最短路径 Dijkstra 对比 SPFA

📖 算法原理：贪心确定性与动态队列松弛

单源最短路算法是图论的核心基础。当图中包含负边权时，算法的物理机制会发生本质的偏转。

📐 Dijkstra 算法 (基于贪心确定性)

核心机制：利用优先队列（堆），每次取出当前 `dist` 最小的未收录点 $u$，标记其为“终极确定 (Finalized)”，并对其所有出边进行松弛。
致命弱点：无法处理负权边。由于贪心机制假设“已被标记确定的顶点距离永远不会再变小”，当负权边隐藏在后面时，被提前确定的节点无法再次松弛，从而导致错误的计算结果。

📐 SPFA 算法 (基于 FIFO 队列松弛)

核心机制：利用常规 FIFO 队列保存“有待继续松弛的节点”。
每步测试：取出队首节点 $u$，松弛其出边 $(u, v)$。如果成功将 $v$ 的距离缩短（dist[v] > dist[u] + w）：
- 更新 dist[v]。
- 若 $v$ 当前不在队列中，将其重新压入队尾（代表该点被更新后可能进而更新它的下级出边）。
优点：能完美处理负权边（只要图中不存在负权回路），节点可多次出入队列重新松弛，直至全局稳定收敛。

演示速度：

点击"开始同步演示"观察左侧的 Dijkstra 贪心错误收录与右侧的 SPFA 循环松弛。

🔴 左屏：Dijkstra 算法 (贪心确定，负权致错)

🌾 priority_queue 优先队列 (小顶堆)

已确定顶点0

终点 6 最终距离INF

🟢 右屏：SPFA 算法 (队列迭代，负权克星)

💧 FIFO queue 常规循环队列

松弛次数0

终点 6 最终距离INF

// SPFA 最短路算法 (基于队列松弛)
void spfa(int start) {
    fill(dist, dist + n + 1, INF);
    dist[start] = 0;
    
    queue<int> q;
    q.push(start); in_queue[start] = true;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        in_queue[u] = false;
        
        for (auto edge : adj[u]) {
            int v = edge.v, w = edge.w;
            if (dist[v] > dist[u] + w) { // 松弛成功！
                dist[v] = dist[u] + w;
                if (!in_queue[v]) { // 若不在队列，则压入重松弛
                    q.push(v);
                    in_queue[v] = true;
                }
            }
        }
    }
}

📋 最短路同步松弛步骤日志