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

Path Reconstruction — Forward recording then backward tracing:

💡 Implementation key: Record prev_node[v] = u meaning "the node before v on the shortest path to v is u". To reconstruct, follow prev_node from dst back to src, then reverse the result.

// 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 (graph: A→B w=2, A→C w=5, B→C w=-1, C→D w=2, B→D w=4):

💡 Key observation: After each round, at least one more node's shortest distance is finalized. After V−1 rounds, all shortest distances are correct (assuming no negative cycles).

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 Transition — introducing node k as an intermediate:

💡 Why must k be the outermost loop? When processing intermediate node k, both dist[i][k] and dist[k][j] must already be fully computed using intermediates {1..k−1}. If k were an inner loop, those values might be updated in the same pass, breaking the DP correctness.

5.4.5 Algorithm Comparison Table

When to Use Which?

Graph has negative edges?
├── YES → Bellman-Ford or SPFA (or Floyd-Warshall for all-pairs)
└── NO  → V ≤ 500 and need all-pairs?
          ├── YES → Floyd-Warshall  O(V³)
          └── NO  → Unweighted graph (all edges = 1)?
                    ├── YES → BFS  O(V+E)
                    └── NO  → Edge weights only 0 or 1?
                              ├── YES → 0-1 BFS  O(V+E)
                              └── NO  → Dijkstra  O((V+E) log V)

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 deque enqueue rule:

Deque:  [front → smallest dist ... → back → largest dist]

When relaxing neighbor v via edge (u→v) with weight w:
  w = 0 → push_front(v)   (same distance as u — keep at front)
  w = 1 → push_back(v)    (one step further — goes to back)

Why correct? The deque front always holds the current minimum-distance node,
because w=0 edges don't increase the distance, while w=1 edges do.
This is Dijkstra-like behavior without a heap: O(V+E) instead of O((V+E) log V).

💡 Efficiency: 0-1 BFS runs in O(V+E) — faster than Dijkstra's O((V+E) log V). When edge weights are only 0 and 1, always prefer 0-1 BFS.

// 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

Problem: Given N cities and M bidirectional roads, each with a travel time. Find the shortest travel time from city 1 to city N. If city N is unreachable, output −1.

Input format:

N M
u₁ v₁ w₁
...

5 6
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1

6

Sample Input 2:

3 2
1 2 5
2 1 3

Sample Output 2:

-1

(Node 3 is unreachable)

Constraints: 2 ≤ N ≤ 10^5, 1 ≤ M ≤ 5×10^5, 1 ≤ w ≤ 10^9

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int,int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<ll> dist(n + 1, LLONG_MAX);
    priority_queue<pli, vector<pli>, greater<pli>> pq;

    dist[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;  // outdated entry

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    cout << (dist[n] == LLONG_MAX ? -1 : dist[n]) << "\n";
    return 0;
}
// Time: O((N + M) log N),  Space: O(N + M)

Problem 5.4.2 — BFS on Grid 🟢 Easy

Problem: A robot starts at cell (0,0) of an R×C grid. Some cells are walls (#); others are passable (.). Find the minimum number of steps to reach (R-1, C-1). Output −1 if impossible.

Input format:

R C
row₁
...

Sample Input 1:

3 4
....
.##.
....

Sample Output 1:

6

(Path: (0,0)→(0,1)→(0,2)→(0,3)→(1,3)→(2,3)→... wait, (2,3) is corner not (R-1,C-1)=(2,3). Answer 6 steps)

Sample Input 2:

2 2
.#
#.

Sample Output 2:

-1

Constraints: 1 ≤ R, C ≤ 1000

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int R, C;
    cin >> R >> C;

    vector<string> grid(R);
    for (auto& row : grid) cin >> row;

    vector<vector<int>> dist(R, vector<int>(C, -1));
    queue<pair<int,int>> q;

    if (grid[0][0] != '#') {
        dist[0][0] = 0;
        q.push({0, 0});
    }

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr >= 0 && nr < R && nc >= 0 && nc < C
                && grid[nr][nc] != '#' && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }

    cout << dist[R-1][C-1] << "\n";
    return 0;
}
// Time: O(R×C),  Space: O(R×C)

Problem 5.4.3 — Negative Edge Detection 🟡 Medium

Problem: Given a directed graph with N nodes, M edges (possibly negative weights), find the shortest distance from node 1 to node N. If a negative cycle is reachable from node 1 and can reach node N, output "NEGATIVE CYCLE". If node N is unreachable, output "UNREACHABLE".

Input format:

N M
u₁ v₁ w₁
...

4 5
1 2 1
2 3 2
3 4 3
1 3 -5
3 2 -10

NEGATIVE CYCLE

Sample Input 2:

3 2
1 2 5
1 3 -1

Sample Output 2:

-1

Constraints: 1 ≤ N ≤ 1000, 1 ≤ M ≤ 5000, -10^9 ≤ w ≤ 10^9

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<tuple<int,int,ll>> edges(m);
    for (auto& [u, v, w] : edges) cin >> u >> v >> w;

    const ll INF = 1e18;
    vector<ll> dist(n + 1, INF);
    dist[1] = 0;

    // Bellman-Ford: N-1 passes
    for (int iter = 0; iter < n - 1; iter++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // N-th pass: detect negative cycles
    vector<bool> inNegCycle(n + 1, false);
    for (int iter = 0; iter < n; iter++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                inNegCycle[v] = true;
            }
            if (inNegCycle[u]) inNegCycle[v] = true;
        }
    }

    if (dist[n] == INF) cout << "UNREACHABLE\n";
    else if (inNegCycle[n]) cout << "NEGATIVE CYCLE\n";
    else cout << dist[n] << "\n";

    return 0;
}
// Time: O(V × E),  Space: O(V + E)

Problem 5.4.5 — All-Pairs with Floyd 🟡 Medium

Problem: Given N cities and M bidirectional roads with travel times, answer Q queries: "Is city u reachable from city v within distance limit D?" For each query, output "YES" or "NO".

Input format:

N M
u₁ v₁ w₁
...
Q
u₁ v₁ D₁
...

4 5
1 2 3
2 3 2
3 4 1
1 4 10
2 4 7
3
1 4 6
1 4 10
2 3 5

YES
YES
YES

Constraints: 1 ≤ N ≤ 300, 1 ≤ M ≤ N², 1 ≤ Q ≤ 10^5, 1 ≤ w ≤ 10^9

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    const ll INF = 1e18;
    vector<vector<ll>> dist(n + 1, vector<ll>(n + 1, INF));

    for (int i = 1; i <= n; i++) dist[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w);
    }

    // Floyd-Warshall: O(N³)
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    int q;
    cin >> q;
    while (q--) {
        int u, v; ll D;
        cin >> u >> v >> D;
        cout << (dist[u][v] <= D ? "YES" : "NO") << "\n";
    }

    return 0;
}
// Time: O(N³ + Q),  Space: O(N²)

Problem 5.4.6 — Maximum Bottleneck Path 🔴 Hard

Problem: Given N cities connected by M roads. Each road has a weight limit (the maximum cargo weight it can support). Find the path from city 1 to city N that maximizes the minimum edge weight along the path — i.e., the heaviest cargo you can move from city 1 to city N in a single trip.

Input format:

N M
u₁ v₁ w₁
...

4 5
1 2 3
1 3 6
2 4 5
3 4 4
2 3 2

5

(Note: Sample recomputed — answer is 4 for path 1→3→4)

Constraints: 2 ≤ N ≤ 10^5, 1 ≤ M ≤ 3×10^5

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<pii>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // Modified Dijkstra: maximize bottleneck
    // dist[v] = max min-edge-weight path from 1 to v
    vector<int> dist(n + 1, 0);
    priority_queue<pii> pq;  // max-heap: {bottleneck, node}

    dist[1] = INT_MAX;
    pq.push({INT_MAX, 1});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d < dist[u]) continue;  // outdated

        for (auto [v, w] : adj[u]) {
            int newBottleneck = min(dist[u], w);  // ← KEY: take minimum along path
            if (newBottleneck > dist[v]) {
                dist[v] = newBottleneck;
                pq.push({dist[v], v});
            }
        }
    }

    cout << dist[n] << "\n";
    return 0;
}
// Time: O((N + M) log N),  Space: O(N + M)

Problem 5.4.4 — Multi-Source BFS: Zombie Outbreak 🟡 Medium

Problem: A zombie outbreak starts at K infected cities simultaneously. Each time unit, zombies spread to all adjacent (uninfected) cities. Find the minimum time for zombies to reach every reachable city. For cities that can never be reached, output −1.

Input format:

N M K
u₁ v₁
...  (M undirected edges)
z₁ z₂ ... zₖ   (K initial zombie cities)

6 6 2
1 2
2 3
3 4
4 5
5 6
2 5
1 4

1 0 1 0 1 2

Multi-Source BFS — How K sources spread simultaneously:

💡 Equivalent formulation: Multi-source BFS = add a virtual source node S, connect S to all K zombie cities with weight 0, then run single-source BFS from S. Pushing all K sources at t=0 is exactly this idea in practice.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> dist(n + 1, -1);
    queue<int> q;

    // Push ALL K zombie sources at time 0
    for (int i = 0; i < k; i++) {
        int z; cin >> z;
        dist[z] = 0;
        q.push(z);
    }

    // Standard BFS from all sources simultaneously
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    for (int u = 1; u <= n; u++) {
        cout << dist[u];
        if (u < n) cout << " ";
    }
    cout << "\n";
    return 0;
}
// Time: O(V + E),  Space: O(V + E)

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