Chapter 5.4: Shortest Paths

Finding the shortest path between nodes is one of the most fundamental problems in graph theory. It appears in GPS navigation, network routing, game AI, and — most importantly for us — USACO problems. This chapter covers four algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall, SPFA) and explains when to use each.

5.4.1 Problem Definition

Single-Source Shortest Path (SSSP)

Given a weighted graph G = (V, E) and a source node s, find the shortest distance from s to every other node.

From source A:

• dist[A] = 0
• dist[B] = 1
• dist[C] = 5
• dist[D] = 5 (A→B→D = 1+4)
• dist[E] = 8 (A→B→D→E = 1+4+3)

Multi-Source Shortest Path (APSP)

Find shortest distances between all pairs of nodes. Used when you need distances from multiple sources, or between every pair.

Why Not Just BFS?

BFS finds shortest path in unweighted graphs (each edge = distance 1). With weights:

• Some paths have many short-weight edges
• Others have few large-weight edges
• BFS ignores weights entirely → wrong answer

5.4.2 Dijkstra's Algorithm

The most important shortest path algorithm. Used in ~90% of USACO problems involving weighted shortest paths.

Core Idea: Greedy + Priority Queue

Dijkstra is a greedy algorithm:

1. Maintain a set of "settled" nodes (shortest distance finalized)
2. Always process the unvisited node with smallest current distance next
3. When processing a node, try to relax its neighbors (update their distances if we found a shorter path)

Why greedy works: If all edge weights are non-negative, the node currently at minimum distance cannot be improved by going through any other node (all alternatives would be ≥ current distance).

Step-by-Step Trace

Start: node 0  |  Initial: dist = [0, ∞, ∞, ∞, ∞]

Final: dist = [0, 4, 2, 3, 6]

Complete Dijkstra Implementation

// Solution: Dijkstra's Algorithm with Priority Queue — O((V+E) log V)
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;   // {distance, node}
typedef long long ll;

const ll INF = 1e18;          // use long long to avoid int overflow!
const int MAXN = 100005;

// Adjacency list: adj[u] = list of {weight, v}
vector<pii> adj[MAXN];

vector<ll> dijkstra(int src, int n) {
    vector<ll> dist(n + 1, INF);   // dist[i] = shortest distance to node i
    dist[src] = 0;
    
    // Min-heap: {distance, node}
    // C++ priority_queue is max-heap by default, so negate to make min-heap
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, src});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();  // get node with minimum distance
        
        // KEY: Skip if we've already found a better path to u
        // (outdated entry in the priority queue)
        if (d > dist[u]) continue;
        
        // Relax all neighbors of u
        for (auto [w, v] : adj[u]) {
            ll newDist = dist[u] + w;
            if (newDist < dist[v]) {
                dist[v] = newDist;          // update distance
                pq.push({newDist, v});       // add updated entry to queue
            }
        }
    }
    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({w, v});
        adj[v].push_back({w, u});  // undirected graph
    }
    
    int src;
    cin >> src;
    
    vector<ll> dist = dijkstra(src, n);
    
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) cout << -1 << "\n";
        else cout << dist[i] << "\n";
    }
    
    return 0;
}

Reconstructing the Shortest Path

路径回溯过程示意：

flowchart LR
    subgraph fwd["正向：Dijkstra 运行时记录 prev_node"]
        direction LR
        S(["src=0"]) -->|"w=2"| C(["2"])
        C -->|"w=1"| D(["3"])
        D -->|"w=1"| B(["1"])
        D -->|"w=3"| E(["4"])
        note_fwd["prev[2]=0, prev[3]=2\nprev[1]=3, prev[4]=3"]
    end
    subgraph back["回溯：从终点倒推到起点"]
        direction RL
        E2(["4"]) -->|"prev[4]=3"| D2(["3"])
        D2 -->|"prev[3]=2"| C2(["2"])
        C2 -->|"prev[2]=0"| S2(["0"])
        note_back["倒序路径: 4→3→2→0\n翻转后: 0→2→3→4"]
    end
    fwd -->|"回溯重建"| back
    style note_back fill:#dcfce7,stroke:#16a34a

💡 实现要点： 记录 prev_node[v] = u 表示“到达 v 的最短路径上，v 的前一个节点是 u”。回溯时从终点不断跟随 prev_node 直到起点，再翻转即得正序路径。

// Solution: Dijkstra with Path Reconstruction
vector<int> prev_node(MAXN, -1);  // prev_node[v] = previous node on shortest path to v

vector<ll> dijkstraWithPath(int src, int n) {
    vector<ll> dist(n + 1, INF);
    dist[src] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, src});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        
        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                prev_node[v] = u;       // track where we came from
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

// Reconstruct path from src to dst
vector<int> getPath(int src, int dst) {
    vector<int> path;
    for (int v = dst; v != -1; v = prev_node[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

// BAD: Processes stale entries in queue
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    // NO CHECK for d > dist[u]!
    // Will re-process nodes with outdated distances
    // Still correct, but O(E log E) instead of O(E log V)
    for (auto [w, v] : adj[u]) {
        if (d + w < dist[v]) {
            dist[v] = d + w;
            pq.push({dist[v], v});
        }
    }
}

// GOOD: Skip outdated priority queue entries
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;  // ← stale entry, skip!
    
    for (auto [w, v] : adj[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}

Key Points for Dijkstra

🚫 CRITICAL: Dijkstra does NOT work with negative edge weights! If any edge weight is negative, Dijkstra may produce incorrect results. The algorithm's correctness relies on the greedy assumption that once a node is settled (popped from the priority queue), its distance is final — negative edges break this assumption. For graphs with negative weights, use Bellman-Ford or SPFA instead.

• Only works with non-negative weights. Negative edges break the greedy assumption (see warning above).
• Use long long for distances when edge weights can be large. dist[u] + w can overflow int.
• Use greater<pii> to make priority_queue a min-heap.
• The if (d > dist[u]) continue; check is essential for correctness and performance.

5.4.3 Bellman-Ford Algorithm

When edges can have negative weights, Dijkstra fails. Bellman-Ford handles negative weights — and even detects negative cycles.

Core Idea: Relaxation V-1 Times

Key insight: any shortest path in a graph with V nodes uses at most V-1 edges (no repeated nodes). So if we relax ALL edges V-1 times, we're guaranteed to find the correct shortest paths.

Algorithm:
1. dist[src] = 0, dist[all others] = INF
2. Repeat V-1 times:
   For every edge (u, v, w):
     if dist[u] + w < dist[v]:
       dist[v] = dist[u] + w   (relax!)
3. Check for negative cycles:
   If ANY edge can still be relaxed → negative cycle exists!

Bellman-Ford Relaxation Process (5 nodes, 6 edges):

flowchart LR
    subgraph iter0["初始状态"]
        direction LR
        A0(["A\ndist=0"]) 
        B0(["B\ndist=∞"])
        C0(["C\ndist=∞"])
        D0(["D\ndist=∞"])
    end
    subgraph iter1["第1轮松弛"]
        direction LR
        A1(["A\ndist=0"])
        B1(["B\ndist=2"])
        C1(["C\ndist=∞→5"])
        D1(["D\ndist=∞"])
    end
    subgraph iter2["第2轮松弛"]
        direction LR
        A2(["A\ndist=0"])
        B2(["B\ndist=2"])
        C2(["C\ndist=5→4"])
        D2(["D\ndist=∞→7"])
    end
    subgraph iter3["第3轮松弛（收敛）"]
        direction LR
        A3(["A\ndist=0"])
        B3(["B\ndist=2"])
        C3(["C\ndist=4"])
        D3(["D\ndist=7→6"])
    end
    iter0 -->|"处理边 A→B(2), A→C(5)"| iter1
    iter1 -->|"处理边 B→C(-1), C→D(2)"| iter2
    iter2 -->|"处理边 B→D(4)"| iter3

💡 关键观察： 每轮松弛后，至少有一个节点的最短距离被确定。V-1 轮后所有节点的最短距离均已确定（前提：无负环）。

Bellman-Ford Implementation

// Solution: Bellman-Ford Algorithm — O(V * E)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef tuple<int, int, int> Edge;  // {from, to, weight}

const ll INF = 1e18;

// Returns shortest distances, or empty if negative cycle detected
vector<ll> bellmanFord(int src, int n, vector<Edge>& edges) {
    vector<ll> dist(n + 1, INF);
    dist[src] = 0;
    
    // Relax all edges V-1 times
    for (int iter = 0; iter < n - 1; iter++) {
        bool updated = false;
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;  // early termination: already converged
    }
    
    // Check for negative cycles (one more relaxation pass)
    for (auto [u, v, w] : edges) {
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            // Negative cycle reachable from source!
            return {};  // signal: negative cycle exists
        }
    }
    
    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    vector<Edge> edges;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
        // For undirected: also add {v, u, w}
    }
    
    int src;
    cin >> src;
    
    vector<ll> dist = bellmanFord(src, n, edges);
    
    if (dist.empty()) {
        cout << "Negative cycle detected!\n";
    } else {
        for (int i = 1; i <= n; i++) {
            cout << (dist[i] == INF ? -1 : dist[i]) << "\n";
        }
    }
    return 0;
}

Why Bellman-Ford Works

After k iterations of the outer loop, dist[v] contains the shortest path from src to v using at most k edges. After V-1 iterations, all shortest paths (which use at most V-1 edges in a cycle-free graph) are found.

Negative Cycle Detection: A negative cycle means you can keep decreasing distance indefinitely. If the V-th relaxation still improves a distance, that node is on or reachable from a negative cycle.

5.4.4 Floyd-Warshall Algorithm

For finding shortest paths between all pairs of nodes.

Core Idea: DP Through Intermediate Nodes

dp[k][i][j] = shortest distance from i to j using only nodes {1, 2, ..., k} as intermediate nodes.

Recurrence:

dp[k][i][j] = min(dp[k-1][i][j],          // don't use node k
                   dp[k-1][i][k] + dp[k-1][k][j])  // use node k

Since we only need the previous layer, we can collapse to 2D:

// Solution: Floyd-Warshall All-Pairs Shortest Path — O(V^3)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1e18;
const int MAXV = 505;

ll dist[MAXV][MAXV];  // dist[i][j] = shortest distance from i to j

void floydWarshall(int n) {
    // ⚠️ CRITICAL: k MUST be the OUTERMOST loop!
    // Invariant: after processing k, dist[i][j] = shortest path from i to j
    //            using only nodes {1..k} as intermediates.
    // If k were inner, dist[i][k] or dist[k][j] might not yet reflect all
    // intermediate nodes up to k-1, breaking the DP correctness.
    for (int k = 1; k <= n; k++) {        // ← OUTER: intermediate node
        for (int i = 1; i <= n; i++) {    // ← MIDDLE: source
            for (int j = 1; j <= n; j++) { // ← INNER: destination
                // Can we go i→k→j faster than i→j directly?
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    // After Floyd-Warshall, dist[i][i] < 0 iff node i is on a negative cycle
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    // Initialize: distance to self = 0, all others = INF
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dist[i][j] = (i == j) ? 0 : INF;
    
    // Read edges
    for (int i = 0; i < m; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);  // handle multiple edges
        dist[v][u] = min(dist[v][u], w);  // undirected
    }
    
    floydWarshall(n);
    
    // Query: shortest path from u to v
    int q; cin >> q;
    while (q--) {
        int u, v; cin >> u >> v;
        cout << (dist[u][v] == INF ? -1 : dist[u][v]) << "\n";
    }
    return 0;
}

Floyd-Warshall Complexity

• Time: O(V³) — three nested loops, each running V times
• Space: O(V²) — the 2D distance array
• Practical limit: V ≤ 500 or so (500³ = 1.25 × 10⁸ is borderline)
• For V > 1000, use Dijkstra from each source: O(V × (V+E) log V)

Floyd-Warshall DP 状态转移示意：

flowchart LR
    subgraph before["引入节点 k 之前"]
        i1([i]) -->|"dist[i][j]"| j1([j])
    end
    subgraph after["引入节点 k 之后"]
        i2([i]) -->|"dist[i][k]"| k2([k])
        k2 -->|"dist[k][j]"| j2([j])
        i2 -.->|"min(dist[i][j],\ndist[i][k]+dist[k][j])"| j2
    end
    before -->|"k 作为中间节点"| after

💡 为什么 k 必须是最外层循环？ 当处理中间节点 k 时，dist[i][k] 和 dist[k][j] 必须已经基于 {1..k-1} 完全计算好。若 k 在内层，这些值可能在同一轮中被修改，破坏 DP 的正确性。

5.4.5 Algorithm Comparison Table

When to Use Which?

flowchart TD
    Start(["图中有负权边？"])
    Start -->|"是"| NegEdge["Bellman-Ford 或 SPFA\n或 Floyd-Warshall（全对）"]
    Start -->|"否"| NoNeg["V ≤ 500 且需要全对最短路？"]
    NoNeg -->|"是"| Floyd["Floyd-Warshall\nO(V³)"]
    NoNeg -->|"否"| Unweighted["无权图（边权=1）？"]
    Unweighted -->|"是"| BFS["BFS\nO(V+E)"]
    Unweighted -->|"否"| ZeroOne["边权只有 0 或 1？"]
    ZeroOne -->|"是"| BFS01["0-1 BFS\nO(V+E)"]
    ZeroOne -->|"否"| Dijkstra["Dijkstra\nO((V+E) log V)"]

    style NegEdge fill:#fef3c7,stroke:#d97706
    style Floyd fill:#dbeafe,stroke:#3b82f6
    style BFS fill:#dcfce7,stroke:#16a34a
    style BFS01 fill:#dcfce7,stroke:#16a34a
    style Dijkstra fill:#f0f4ff,stroke:#4A6CF7

5.4.6 SPFA — Bellman-Ford with Queue Optimization

SPFA (Shortest Path Faster Algorithm) is an optimized Bellman-Ford that only adds a node to the queue when its distance is updated, avoiding redundant relaxations.

⚠️ SPFA Worst Case: SPFA's worst-case time complexity is O(V × E) — identical to plain Bellman-Ford. On adversarially constructed graphs (common in competitive programming "anti-SPFA" test cases), SPFA degrades to O(VE) and may TLE. A node can enter the queue up to V times; with E edges processed per queue entry, the total is O(VE). In most random/practical cases it's fast (O(E) average), but for USACO, prefer Dijkstra when all weights are non-negative.

// Solution: SPFA (Bellman-Ford + Queue Optimization)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;

const ll INF = 1e18;
const int MAXN = 100005;
vector<pii> adj[MAXN];

vector<ll> spfa(int src, int n) {
    vector<ll> dist(n + 1, INF);
    vector<bool> inQueue(n + 1, false);
    vector<int> cnt(n + 1, 0);   // cnt[v] = number of times v entered queue
    
    queue<int> q;
    dist[src] = 0;
    q.push(src);
    inQueue[src] = true;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inQueue[u] = false;
        
        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    cnt[v]++;
                    
                    // Negative cycle detection: if a node enters queue >= n times
                    // (a node can enter at most n-1 times without a neg cycle;
                    //  using > n is also safe but detects one step later)
                    if (cnt[v] >= n) return {};  // negative cycle!
                }
            }
        }
    }
    return dist;
}

5.4.7 BFS as Dijkstra for Unweighted Graphs

When all edge weights are 1 (unweighted graph), BFS is exactly Dijkstra with a simple queue:

• Dijkstra's priority queue naturally processes nodes in order of distance
• In an unweighted graph, all edges have weight 1, so nodes at distance d are processed before distance d+1
• BFS naturally explores level-by-level, which is exactly "by distance"

// Solution: BFS for Unweighted Shortest Path — O(V + E)
// Equivalent to Dijkstra when all weights = 1
vector<int> bfsShortestPath(int src, int n) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    
    dist[src] = 0;
    q.push(src);
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        
        for (auto [w, v] : adj[u]) {
            if (dist[v] == -1) {       // unvisited
                dist[v] = dist[u] + 1; // all weights = 1
                q.push(v);
            }
        }
    }
    return dist;
}

Why is BFS correct for unweighted graphs? Because BFS explores nodes in strictly increasing order of their distance. The first time you reach a node v, you've found the shortest path (fewest edges = minimum distance when all weights are 1).

0-1 BFS: A powerful trick when edge weights are only 0 or 1 (use deque instead of queue):

0-1 BFS 双端队列操作示意：

flowchart LR
    subgraph dq["双端队列 deque 状态"]
        direction LR
        Front[["队首（小距离）"]] --- M1["..."] --- M2["..."] --- Back[["队尾（大距离）"]]
    end
    subgraph rule["入队规则"]
        direction TB
        W0["边权 w=0\n→ push_front（加队首）"] 
        W1["边权 w=1\n→ push_back（加队尾）"]
    end
    subgraph why["为什么正确？"]
        direction TB
        Exp["队首始终是当前最小距离的节点\nw=0 边不增加距离，应与当前节点同优先级\nw=1 边增加距离，排到队尾等待"]
    end
    rule --> dq
    dq --> why
    style W0 fill:#dbeafe,stroke:#3b82f6
    style W1 fill:#fef3c7,stroke:#d97706

💡 效率对比： 0-1 BFS 为 O(V+E)，比 Dijkstra 的 O((V+E) log V) 更快。当边权只有 0 和 1 时，优先选用此方法。

// Solution: 0-1 BFS — O(V + E), handles {0,1} weight edges
vector<int> bfs01(int src, int n) {
    vector<int> dist(n + 1, INT_MAX);
    deque<int> dq;
    
    dist[src] = 0;
    dq.push_front(src);
    
    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        
        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);   // 0-weight: add to front
                else        dq.push_back(v);    // 1-weight: add to back
            }
        }
    }
    return dist;
}

5.4.8 USACO Example: Farm Tours

Problem Statement (USACO 2003 Style)

Farmer John wants to take a round trip: travel from farm 1 to farm N, then return from N to farm 1, using no road twice. Roads are bidirectional. Find the minimum total distance of such a round trip.

Constraints: N ≤ 1000, M ≤ 10,000, weights ≤ 1000.

Input Format:

N M
u1 v1 w1
u2 v2 w2
...

Analysis:

• We need to go 1→N and N→1 without repeating any edge
• Key insight: this equals finding two edge-disjoint paths from 1 to N with minimum total cost
• Alternative insight: the "return trip" N→1 is just another path 1→N in the original graph
• Simplification for this problem: Find the shortest path from 1 to N twice, but with different edges

For this USACO-style problem, a simpler interpretation: since roads are bidirectional and we can use each road at most once in each direction, find:

• Shortest path 1→N
• Shortest path N→1 (using possibly different roads)
• These can be found independently with Dijkstra

But the real challenge: "using no road twice" means globally, not just per direction.

Greedy approach for this version: Find shortest path 1→N, then find shortest path on remaining graph N→1. This greedy doesn't always work, but for USACO Bronze/Silver, many problems simplify to just running Dijkstra twice.

// Solution: Farm Tours — Two Dijkstra (simplified version)
// Run Dijkstra from both endpoints, find min round-trip distance
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, int> pli;
const ll INF = 1e18;
const int MAXN = 1005;

vector<pair<int,int>> adj[MAXN];  // {weight, dest}

vector<ll> dijkstra(int src, int n) {
    vector<ll> dist(n + 1, INF);
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    dist[src] = 0;
    pq.push({0, src});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        
        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({w, v});
        adj[v].push_back({w, u});  // bidirectional
    }
    
    // Run Dijkstra from farm 1 and farm N
    vector<ll> distFrom1 = dijkstra(1, n);
    vector<ll> distFromN = dijkstra(n, n);
    
    // Find intermediate farm that minimizes: dist(1,k) + dist(k,N) + dist(N,k) + dist(k,1)
    // = 2 * (dist(1,k) + dist(k,N)) ... but this is just going via k twice
    
    // Simplest: answer is distFrom1[n] + distFromN[1]
    // (Go 1→N one way, return N→1 by shortest path — may reuse edges)
    ll answer = distFrom1[n] + distFromN[1];
    
    if (answer >= INF) cout << "NO VALID TRIP\n";
    else cout << answer << "\n";
    
    // For the "no road reuse" constraint, see flow algorithms (beyond Silver)
    
    return 0;
}

5.4.9 Dijkstra on Grids

Many USACO problems involve grid-based shortest paths. The graph is implicit:

// Solution: Dijkstra on Grid — find shortest path from (0,0) to (R-1,C-1)
// Each cell has a "cost" to enter
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef tuple<ll,int,int> tli;

const ll INF = 1e18;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

ll dijkstraGrid(vector<vector<int>>& grid) {
    int R = grid.size(), C = grid[0].size();
    vector<vector<ll>> dist(R, vector<ll>(C, INF));
    priority_queue<tli, vector<tli>, greater<tli>> pq;
    
    dist[0][0] = grid[0][0];
    pq.push({grid[0][0], 0, 0});
    
    while (!pq.empty()) {
        auto [d, r, c] = pq.top(); pq.pop();
        if (d > dist[r][c]) continue;
        
        for (int k = 0; k < 4; k++) {
            int nr = r + dx[k], nc = c + dy[k];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            
            ll newDist = dist[r][c] + grid[nr][nc];
            if (newDist < dist[nr][nc]) {
                dist[nr][nc] = newDist;
                pq.push({newDist, nr, nc});
            }
        }
    }
    return dist[R-1][C-1];
}

⚠️ Common Mistakes — The Dirty Five

// BAD: int overflow when adding large distances
vector<int> dist(n+1, 1e9);  // use int

// dist[u] = 9×10^8, w = 9×10^8
// dist[u] + w overflows int!
if (dist[u] + w < dist[v]) { ... }

// GOOD: always use long long for distances
const ll INF = 1e18;
vector<ll> dist(n+1, INF);

// No overflow with long long (max ~9.2×10^18)
if (dist[u] + w < dist[v]) { ... }

// BAD: This is a MAX-heap, not min-heap!
priority_queue<pii> pq;   // default is max-heap
pq.push({dist[v], v});
// Will process FARTHEST node first — wrong!

// GOOD: explicitly specify min-heap
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({dist[v], v});
// Now processes NEAREST node first ✓

5 Classic Dijkstra Bugs:

1. Using int instead of long long — distance sum overflows → wrong answers silently
2. Max-heap instead of min-heap — forgetting greater<pii> → processes wrong node first
3. Missing stale entry check (if (d > dist[u]) continue) → not wrong but ~10x slower
4. Forgetting dist[src] = 0 — all distances remain INF
5. Using Dijkstra with negative edges — undefined behavior, may loop infinitely or give wrong answer

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: Why can't Dijkstra handle negative edges?

A: Dijkstra's greedy assumption is "the node with the current shortest distance cannot be improved by later paths." With negative edges, this assumption fails—a longer path through a negative edge may end up shorter.

Concrete counterexample: Nodes A, B, C. Edges: A→B=2, A→C=10, B→C=−20.

• Dijkstra processes A first (dist=0), relaxes to dist[B]=2, dist[C]=10
• Then processes B (dist=2, minimum), relaxes to dist[C]=min(10, 2+(-20))=-18
• But if Dijkstra "settles" C before processing B (this specific case won't, but slightly different weights will cause issues)

General explanation: When node u is popped and settled, Dijkstra considers dist[u] optimal. But if there is a negative edge (v, u, w) with w < 0, there may be a path src→...→v→u with total weight < current dist[u], while v has not yet been processed.

Conclusion: With negative edges, you must use Bellman-Ford (O(VE)) or SPFA (average O(E), worst O(VE)).

Q2: What is the difference between SPFA and Bellman-Ford?

A: SPFA is a queue-optimized version of Bellman-Ford. Bellman-Ford traverses all edges each round; SPFA only updates neighbors of nodes whose distance improved, using a queue to track which nodes need processing. In practice SPFA is much faster (average O(E)), but the theoretical worst case is the same (O(VE)). On some contest platforms SPFA can be hacked to worst case, so with negative edges consider Bellman-Ford; without negative edges always use Dijkstra.

Q3: Why must the k loop be the outermost in Floyd-Warshall?

A: This is the most common Floyd-Warshall implementation error! The DP invariant is: after the k-th outer loop iteration, dist[i][j] represents the shortest path from i to j using only nodes {1, 2, ..., k} as intermediates. When processing intermediate node k, dist[i][k] and dist[k][j] must already be fully computed based on {1..k-1}. If k is in the inner loop, dist[i][k] may have just been updated in the same outer loop iteration, leading to incorrect results. Remember: k is outermost, i and j are inner — order matters!

Q4: How to determine whether a USACO problem needs Dijkstra or BFS?

A: Key question: Are edges weighted?

• Unweighted graph (edge weight=1 or find minimum edges) → BFS, O(V+E), faster and simpler code
• Weighted graph (different non-negative weights) → Dijkstra
• Edge weights only 0 or 1 → 0-1 BFS (faster than Dijkstra, O(V+E))
• Has negative edges → Bellman-Ford/SPFA

Q5: When to use Floyd-Warshall?

A: When you need shortest distances between all pairs, and V ≤ 500 (since O(V³) ≈ 1.25×10⁸ is barely feasible at V=500). Typical scenario: given multiple sources and targets, query distance between any pair. For V > 500, run Dijkstra once per node (O(V × (V+E) log V)) is faster.

🔗 Connections to Other Chapters

• Chapter 5.2 (BFS & DFS): BFS is "Dijkstra for unweighted graphs"; this chapter is a direct extension of BFS
• Chapter 3.11 (Binary Trees): Dijkstra's priority queue is a binary heap; understanding heaps helps analyze complexity
• Chapter 5.3 (Trees & Special Graphs): Shortest path on a tree is the unique root-to-node path (DFS/BFS suffices)
• Chapter 6.1 (DP Introduction): Floyd-Warshall is essentially DP (state = "using first k nodes"); many shortest path variants can be modeled with DP
• USACO Gold: Shortest path + DP combinations (e.g., DP on shortest path DAG), shortest path + binary search, shortest path + data structure optimization

Practice Problems

Problem 5.4.1 — Classic Dijkstra 🟢 Easy Given N cities and M roads with travel time, find the shortest travel time from city 1 to city N. If unreachable, output -1. (N ≤ 10^5, M ≤ 5×10^5, weights ≤ 10^9)

Problem 5.4.2 — BFS on Grid 🟢 Easy A robot is on an R×C grid. Some cells are walls. Find the shortest path (in steps) from top-left to bottom-right. Output -1 if impossible.

Problem 5.4.3 — Negative Edge Detection 🟡 Medium Given a directed graph with possibly negative edge weights, determine:

1. The shortest distance from node 1 to node N
2. Whether any negative cycle exists that is reachable from node 1

Problem 5.4.4 — Multi-Source BFS 🟡 Medium A zombie outbreak starts at K infected cities. Find the minimum time for zombies to reach each city (spread 1 city per time unit via roads).

多源 BFS 扩散过程示意：

flowchart LR
    subgraph t0["初始：K个感染源同时入队"]
        direction TB
        Z1(["Z1\nt=0"]) 
        Z2(["Z2\nt=0"])
        Z3(["Z3\nt=0"])
        note0["queue = [Z1, Z2, Z3]"]
    end
    subgraph t1["第 1 轮：向外扩散"]
        direction TB
        A1(["Z1\nt=0"]) --- B1(["A\nt=1"])
        C1(["Z2\nt=0"]) --- D1(["B\nt=1"])
        E1(["Z3\nt=0"]) --- F1(["C\nt=1"])
    end
    subgraph t2["第 2 轮：继续扩散"]
        direction TB
        G2(["A\nt=1"]) --- H2(["D\nt=2"])
        I2(["B\nt=1"]) --- J2(["E\nt=2"])
        note2["已访问节点不再入队"]
    end
    t0 --> t1 --> t2
    style Z1 fill:#fef2f2,stroke:#dc2626
    style Z2 fill:#fef2f2,stroke:#dc2626
    style Z3 fill:#fef2f2,stroke:#dc2626

💡 等价转化： 多源 BFS = 添加一个虚拟起点 S，将 S 以距离 0 连接到所有 K 个感染源，再运行单源 BFS。所有感染源同时入队就是这个思路的实现。

Problem 5.4.5 — All-Pairs with Floyd 🟡 Medium Given N cities (N ≤ 300) and M roads, answer Q queries: "Is city u reachable from city v within distance D?"

Problem 5.4.6 — Dijkstra + Binary Search 🔴 Hard A delivery drone can carry a maximum weight of W. There are N cities connected by roads, each road has a weight limit. Find the path from city 1 to city N that maximizes the minimum weight limit along the path (i.e., the heaviest cargo the drone can carry).

End of Chapter 5.4 — Next: Chapter 6.1: Introduction to DP