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)

All-Pairs Shortest Path (APSP)

Find the shortest distance between every pair of nodes.

Why Not Just BFS?

BFS finds shortest paths 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

// Dijkstra's Algorithm (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}
    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 outdated entries (a better path to u was already found)
        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});       // push updated entry into queue
            }
        }
    }
    return dist;
}

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 popped from the priority queue (settled), its distance is final — negative edges break this assumption. For graphs with negative edges, use Bellman-Ford or SPFA instead.

• Only works with non-negative weights. Negative edges break the greedy assumption.
• 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

A single-source shortest-path algorithm that is slower than Dijkstra but handles negative-weight edges and can even detect negative cycles.

Core Idea

Bellman-Ford does only one thing, and does it repeatedly:

Go through every edge; if using edge u→v makes dist[v] smaller, update dist[v]. This operation is called relaxation.

if (dist[u] != INF && dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;  // relax
}

Relaxation is simple: given the distance to u, try "go to u first, then take the edge to v"; if that's shorter than the current distance to v, update it.

Why Repeat V-1 Rounds?

One round of relaxation can only propagate known distances one edge outward:

• After round 1: we've found every shortest path that uses at most 1 edge
• After round 2: every shortest path that uses at most 2 edges
• After round k: every shortest path that uses at most k edges

With no negative cycles, a shortest path never revisits a node and uses at most V-1 edges. So V-1 rounds are always enough.

Why Not Dijkstra?

Dijkstra finalizes a node's distance as soon as it's settled. But negative edges mean "a longer detour can still be shorter", breaking that assumption.

A → B weight 10,  A → C weight 5,  C → B weight -3

The shortest path from A to B is A→C→B = 2, not the direct A→B = 10. Dijkstra may lock in B=10 early and miss the better route.

Bellman-Ford never locks anything in early; every round re-examines every edge, so it handles negative weights correctly.

Step-by-Step Trace

Edges: A→B(4), A→C(2), A→F(15), C→B(1), B→D(5), C→D(8), B→E(7), D→E(-6), D→F(4), E→F(2); source A.

Final shortest path: A→C→B→D→E→F = 2+1+5+(-6)+2 = 4.

Key takeaways:

• Direct ≠ shortest: F starts at 15, ends at 4
• Negative edges amplify improvements: once D becomes shorter, D→E(-6) slashes dist[E]
• V-1 rounds is an upper bound: 6 nodes allow at most 5 rounds; here we converged in round 4

Algorithm Outline

Bellman-Ford(src):
  1. dist[src] = 0, all others = ∞
  2. Repeat V-1 times: iterate every edge and try to relax
  3. One more pass: if any edge still relaxes → negative cycle exists

Negative Cycle Detection

A negative cycle is a cycle whose total weight is negative; looping around it makes the distance smaller every time, so no shortest path exists.

A→B(2), B→C(-5), C→A(1) → cycle total = -2

Detection method: after V-1 rounds, all shortest paths should have stabilized. If a V-th pass still relaxes an edge, a negative cycle reachable from the source exists.

for (auto& [u, v, w] : edges) {
    if (dist[u] != INF && dist[u] + w < dist[v]) {
        return {};  // negative cycle!
    }
}

⚠️ This method only detects negative cycles reachable from the source. To detect any negative cycle in the graph, use the "super-source" trick (see the SPFA section).

Complete Implementation

// 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-distance array, or empty if a negative cycle is detected
vector<ll> bellmanFord(int src, int n, vector<Edge>& edges) {
    vector<ll> dist(n + 1, INF);
    dist[src] = 0;

    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 convergence
    }

    // V-th pass: detect negative cycle reachable from the source
    for (auto& [u, v, w] : edges) {
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            return {};  // negative cycle!
        }
    }

    return dist;
}

When to Use Bellman-Ford

• No negative edges → Dijkstra is faster
• Negative edges but no negative cycle, single-source shortest path → Bellman-Ford or SPFA
• Need to detect negative cycles reachable from the source → Bellman-Ford
• Very large graph → O(VE) may TLE; consider SPFA or other techniques

💡 In one sentence: Relax every edge each round; round k guarantees all shortest paths that use ≤ k edges, so V-1 rounds always converge. If the V-th pass still relaxes, a negative cycle exists.

5.4.4 Floyd-Warshall Algorithm

Computes shortest paths between all pairs of nodes in one go.

Core Idea: Try Every Node as a Relay

Imagine you want to find the shortest route between every pair of cities in a country. The simplest approach: for each pair (i, j), check if there's a direct road. But that only considers direct routes.

Key insight: the shortest path from i to j either goes directly, or passes through some relay node k:

shortest i→j = min( direct i→j,  via relay i→k→j )

Floyd-Warshall systematizes this: try each node k as a relay and see if i→k→j is shorter than the current i→j.

if (dist[i][k] + dist[k][j] < dist[i][j]) {
    dist[i][j] = dist[i][k] + dist[k][j];  // going via k is shorter, update
}

Step-by-Step Trace

4 nodes (0–3), 5 undirected edges: 0-1(3), 0-2(8), 1-2(2), 1-3(5), 2-3(1)

Initial distance matrix (only direct edges filled, no direct edge = ∞):

k=0: Use node 0 as relay. Check all (i,j) pairs: can i→0→j beat i→j?

k=0: no updates. Matrix unchanged.

k=1: Use node 1 as relay.

Matrix after k=1:

k=2: Use node 2 as relay.

Matrix after k=2:

k=3: Use node 3 as relay. All checks yield no shorter paths. Matrix unchanged.

Final result: dist[0][3]=6 (path 0→1→2→3), dist[1][3]=3 (path 1→2→3)

Why Must k Be the Outermost Loop?

This is the most common implementation mistake in Floyd-Warshall.

The key: when processing relay node k, dist[i][k] and dist[k][j] must still be the values computed before trying k as a relay (i.e., using only {0..k-1} as relays).

• k outermost ✅: When processing k, the i-j loops only read dist[i][k] and dist[k][j]. These won't be modified during the current k-round (row k and column k depend only on {0..k-1}), so they're safe to use.
• k innermost ❌: Within the same k-round, a just-updated dist[i][k] gets read by a later (i', j') check, which is like "using k as a relay twice in the same round" — incorrect results.

Remember: k is outermost, i and j are inner — order matters!

Complete Implementation

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

void floydWarshall(int n) {
    // Initialize: dist[i][i]=0, edges set to weight, non-edges = INF
    // ... (done during input reading)

    // ⚠️ CRITICAL: k MUST be the OUTERMOST loop!
    for (int k = 1; k <= n; k++) {         // relay node
        for (int i = 1; i <= n; i++) {     // source
            for (int j = 1; j <= n; j++) { // destination
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    // If dist[i][i] < 0 after running, node i is on a negative cycle
}

When to Use Floyd-Warshall?

• Need all-pairs shortest paths and V ≤ 500 (V³ ≈ 1.25×10⁸ is borderline)
• V > 500: run Dijkstra from each source — O(V × (V+E) log V) is faster
• Need to detect graph-wide negative cycles: after running, check dist[i][i] < 0
• Extremely short code: only 5 lines of core logic, great for small-V problems

💡 One-line summary: Try each node k as a relay — if i→k→j is shorter than current i→j, update. Triple loop, k must be outermost.

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

In the previous section we learned Bellman-Ford: scan all edges every round, repeat V-1 rounds. You might wonder — most edges don't produce any relaxation in a given round, so scanning them is pure waste. SPFA fixes exactly this.

From Bellman-Ford to SPFA: An Intuition

What Bellman-Ford does each round: iterate all E edges and check which ones can relax.

But think about it: only a node u whose dist just decreased can possibly relax its neighbors v. If dist[u] didn't change this round, its neighbors won't improve either.

SPFA's core idea: whenever a node's distance is updated, enqueue it. When dequeuing a node, relax only its neighbors. Nodes whose distances haven't changed are simply ignored.

On the left, Bellman-Ford scans 6 edges per round — 30 checks across 5 rounds. On the right, SPFA only processes neighbors of updated nodes — about 12 checks total. Same results, far less work.

How the Queue Works

SPFA's structure is almost identical to BFS. The only difference: in BFS every node is enqueued exactly once; in SPFA a node can be enqueued multiple times (because its distance may be improved repeatedly).

Key details:

Step-by-Step Trace

Below we run SPFA on the exact same graph as Bellman-Ford, so you can compare the two algorithms side by side.

Final result: A→C→B→D→E→F = 2+1+5+(-6)+2 = 4 — identical to Bellman-Ford.

💡 Compared to Bellman-Ford: BF ran 5 rounds × 10 edges = 50 edge checks; SPFA did only ~18. The larger and sparser the graph, the bigger SPFA's advantage.

Negative Cycle Detection

Like Bellman-Ford, SPFA can also detect negative cycles:

• Principle: Without a negative cycle, a node can be enqueued at most V-1 times (corresponding to a shortest path with at most V-1 edges)
• Criterion: If a node is enqueued ≥ V times, a negative cycle exists

cnt[v]++;
if (cnt[v] >= n) return {};  // negative cycle!

⚠️ The code above detects negative cycles reachable from src. To detect any negative cycle in the graph (including unreachable parts), use a super-source — see below.

Complete Implementation

// SPFA (Bellman-Ford + queue optimization)
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] = how many times v entered the 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: a node entering the queue >= n times
                    if (cnt[v] >= n) return {};  // negative cycle!
                }
            }
        }
    }
    return dist;
}

Negative Cycle Detection for the Entire Graph

The SPFA above detects negative cycles reachable from src. To check whether the whole graph contains any negative cycle (including parts unreachable from src), set up a super-source:

// Detect a negative cycle anywhere (including unreachable parts).
// Add super-source 0 with 0-weight edges to every node, and run Bellman-Ford from 0.
bool hasNegativeCycle(int n) {
    // Original nodes are 1..n; super-source is 0
    vector<ll> dist(n + 1, 0);  // all start at 0 (equivalent to 0-weight edges from super-source)
    vector<bool> inQueue(n + 1, true);
    vector<int> cnt(n + 1, 0);
    queue<int> q;

    // Push every node (super-source effect)
    for (int i = 1; i <= n; i++) q.push(i);

    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;
                    if (++cnt[v] >= n) return true;  // negative cycle!
                }
            }
        }
    }
    return false;
}

When to Use SPFA

• All edges non-negative → Dijkstra is more stable
• Negative edges but no negative cycle, single-source shortest path → SPFA is the first choice (much faster than Bellman-Ford)
• Need to detect negative cycles reachable from the source → SPFA (enqueue-count criterion)
• Need to detect any negative cycle in the graph → Super-source + SPFA

⚠️ SPFA Worst Case: The worst-case time complexity is O(V × E) — identical to plain Bellman-Ford. On adversarially constructed graphs (common in competitive-programming "anti-SPFA" test data), SPFA degrades and may TLE. So: use Dijkstra whenever possible; only consider SPFA when negative edges exist.

💡 In one sentence: Bellman-Ford scans all edges every round; SPFA only relaxes neighbors of just-updated nodes — using a queue to skip useless edges, producing the same result, usually much faster.

5.4.7 Johnson's Algorithm — All-Pairs Shortest Paths

Floyd-Warshall is O(N³); running N Bellman-Fords is O(N²M). Johnson's algorithm reweights edges so that N runs of Dijkstra work on a graph with no negative edges, for a total of O(NM log M) — better than Floyd on sparse graphs.

Algorithm Steps

1. Add a super-source 0 with 0-weight edges to every node
2. Run Bellman-Ford from 0 to compute h[i] = shortest distance from 0 to each node (if a negative cycle exists, no solution)
3. Reweight edges: w'(u,v) = w(u,v) + h[u] - h[v] (guaranteed ≥ 0)
4. Run Dijkstra from each node as a source (N times)
5. Restore the real answer: actual shortest path = Dijkstra result − h[s] + h[t]

// Johnson's All-Pairs Shortest Paths — O(NM log M)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

int n, m;
// adj[u] = {v, w}; edges stores all edges for Bellman-Ford
vector<pair<int,ll>> adj[505];
struct Edge { int u, v; ll w; };
vector<Edge> edges;

vector<ll> bellman_ford(int s) {
    vector<ll> dist(n + 1, INF);
    dist[s] = 0;
    for (int i = 0; i < n; i++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }
    return dist;
}

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

// Returns dist[i][j] = true shortest path from i to j
// Returns INF if j is unreachable from i
vector<vector<ll>> johnson() {
    // Super-source n+1 with 0-weight edges to every node
    for (int i = 1; i <= n; i++)
        edges.push_back({n + 1, i, 0});

    // Bellman-Ford to get the potential h[]
    vector<ll> h = bellman_ford(n + 1);

    // Reweight edges (guaranteed non-negative)
    for (auto& e : edges) {
        if (e.u != n + 1)  // skip virtual edges from the super-source
            e.w += h[e.u] - h[e.v];
    }
    // Sync the adjacency list
    for (int u = 1; u <= n; u++)
        for (auto& [v, w] : adj[u])
            w += h[u] - h[v];

    // N runs of Dijkstra
    vector<vector<ll>> ans(n + 1, vector<ll>(n + 1, INF));
    for (int s = 1; s <= n; s++) {
        auto d = dijkstra(s, n);
        for (int t = 1; t <= n; t++) {
            if (d[t] != INF)
                ans[s][t] = d[t] - h[s] + h[t];  // restore true distance
        }
    }
    return ans;
}

💡 Why are reweighted edges non-negative? The triangle inequality gives h[v] ≤ h[u] + w(u,v), so w'(u,v) = w(u,v) + h[u] - h[v] ≥ 0.

5.4.8 Reconstructing the Shortest Path

Use a pre[] array to record each node's predecessor, updated during relaxation:

// Dijkstra with path reconstruction
vector<int> dijkstra_with_path(int src, int dst, int n) {
    vector<ll> dist(n + 1, INF);
    vector<int> pre(n + 1, -1);  // pre[v] = predecessor of v
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> 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 [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pre[v] = u;          // record predecessor
                pq.push({dist[v], v});
            }
        }
    }

    // Reconstruct path from pre[] (reversed)
    vector<int> path;
    for (int v = dst; v != -1; v = pre[v])
        path.push_back(v);
    reverse(path.begin(), path.end());

    // Check the path actually starts at src
    if (path.empty() || path[0] != src) return {};  // unreachable
    return path;  // src → ... → dst
}

When all edge weights are 1 (unweighted graph), BFS is just Dijkstra with a plain queue.

0-1 BFS: A powerful trick when edge weights are only 0 or 1, using a deque instead of a queue:

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

Relax neighbor v (via edge u→v of weight w):
  w = 0 → push_front(v)   (same distance as u — goes to the front)
  w = 1 → push_back(v)    (one step further — goes to the back)

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

// 0-1 BFS — O(V + E) for {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: push front
                else        dq.push_back(v);    // 1-weight: push back
            }
        }
    }
    return dist;
}

5.4.8 Dijkstra on Grids

Many USACO problems involve grid-based shortest paths; the graph is implicit:

// Grid Dijkstra — shortest path from (0,0) to (R-1,C-1)
// Each cell has an entry cost
#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];
}

⚠️ Five Classic Dijkstra Bugs

1. Using int instead of long long — distance sums overflow → silently wrong answers
2. Max-heap instead of min-heap — forgetting greater<pii> → processes the wrong node first
3. Missing the stale-entry check (if (d > dist[u]) continue) — not wrong, but roughly 10× slower
4. Forgetting dist[src] = 0 — every distance stays INF
5. Using Dijkstra with negative edges — undefined behavior; may infinite-loop or return wrong answers

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. 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)).

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 5.4 (Binary Trees & Tree Algorithms): 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 combos, 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. Output −1 if unreachable.

Sample Input 1:

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

Sample Output 1: 6 (shortest path: 1→2→3→5, cost 2+1+3=6)

Sample Input 2: 3 cities, node 3 unreachable → Output: -1

#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;

        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.

#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;
}

Problem 5.4.3 — Negative Edge Detection 🟡 Medium

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

#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: V-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;
            }
        }
    }

    // V-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;
}

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; output −1 for cities that can never be reached.

#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;
}

Problem 5.4.5 — All-Pairs with Floyd 🟡 Medium

Problem: Given N cities (N ≤ 300) and M roads, answer Q queries: "Is the distance between cities u and v at most D?"

#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 with a weight limit (the maximum cargo weight it can carry), find the path from city 1 to city N that maximizes the minimum edge weight along the path — i.e., the heaviest cargo that can be shipped in one trip.

#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
    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;

        for (auto [v, w] : adj[u]) {
            int newBottleneck = min(dist[u], w);  // ← KEY: min along the 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)

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