Shortest Path (Dijkstra, Bellman-Ford, Floyd-Warshall)
Shortest Path Algorithms -- Complete Guide
Shortest path problems are among the most fundamental in graph theory and competitive programming. This guide covers every major algorithm in depth: when to use each one, why it works, how to implement it, and where it breaks down.
Overview: Which Algorithm When?
The Mental Model
Think of shortest paths as a "wavefront" expanding from the source:
1. BFS -- Shortest Path in Unweighted Graphs
Why BFS Gives Shortest Paths
BFS explores nodes in order of their distance from the source. When every edge has weight 1, the first time we reach a node is guaranteed to be via the shortest path.
Proof sketch: BFS processes nodes at distance 0, then distance 1, then distance 2, ... A node at distance d is only reachable from nodes at distance d-1 (which are already processed). So the first time we see a node, we see it at its true shortest distance.
BFS from S:
Layer 0: {S} dist = 0
Layer 1: {A, B} dist = 1
Layer 2: {D, C, F} dist = 2
Layer 3: {E, G} dist = 3
Layer 4: {H} dist = 4
Queue progression:
[S] -> [A, B] -> [B, D, C] -> [D, C, F] -> [C, F] -> [F, E] -> [E, G] -> [G, H] -> [H]
Implementation
CPP
#include <bits/stdc++.h>
using namespace std;
// Returns shortest distances from 'start' to all nodes.
// dist[v] = -1 means v is unreachable.
vector<int> bfsShortestPath(int start, vector<vector<int>>& adj, int n) {
vector<int> dist(n, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
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);
}
}
}
return dist;
}
// With path reconstruction
pair<vector<int>, vector<int>> bfsWithPath(int start, vector<vector<int>>& adj, int n) {
vector<int> dist(n, -1), parent(n, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
parent[v] = u;
q.push(v);
}
}
}
return {dist, parent};
}
vector<int> reconstructPath(int source, int target, vector<int>& parent) {
if (parent[target] == -1 && target != source) return {}; // unreachable
vector<int> path;
for (int v = target; v != -1; v = parent[v])
path.push_back(v);
reverse(path.begin(), path.end());
return path;
}
Complexity
- Time: O(V + E) -- each vertex and edge is processed exactly once
- Space: O(V) for the distance array and queue
2. 0-1 BFS -- When Edges Have Weight 0 or 1
The Insight
When edge weights are only 0 or 1, we can avoid a full priority queue. Instead, use a deque (double-ended queue):
- Weight-0 edges: push to the front (same distance layer)
- Weight-1 edges: push to the back (next distance layer)
This maintains the invariant that the deque is sorted by distance, just like BFS maintains sorted layers.
Why it works:
Regular BFS queue at any time: [d, d, d, d+1, d+1, d+1]
^front ^back
0-1 BFS deque: [d, d, d, d+1, d+1, d+1]
^front ^back
Weight-0 edge from d -> d: push_front -> [d, d, d, d, d+1, d+1, d+1]
Weight-1 edge from d -> d+1: push_back -> [d, d, d, d+1, d+1, d+1, d+1]
The deque always has at most 2 distinct distance values!
Visual Walkthrough
0-1 BFS from A:
Deque: [(0,A)]
Pop A (dist=0):
Edge A->B (w=0): dist[B] = 0, push_front
Edge A->C (w=1): dist[C] = 1, push_back
Deque: [(0,B), (1,C)]
Pop B (dist=0):
Edge B->E (w=1): dist[E] = 1, push_back
Deque: [(1,C), (1,E)]
Pop C (dist=1):
Edge C->D (w=0): dist[D] = 1, push_front
Deque: [(1,D), (1,E)]
Pop D (dist=1):
Edge D->F (w=1): dist[F] = 2, push_back
Deque: [(1,E), (2,F)]
Pop E (dist=1):
Edge E->F (w=0): dist[F] = min(2,1) = 1
But dist[F] was 2, now 1 -> push_front
Deque: [(1,F)]
Pop F (dist=1): done.
Final: A=0, B=0, C=1, D=1, E=1, F=1
Implementation
CPP
vector<int> bfs01(int start, vector<vector<pair<int,int>>>& adj, int n) {
vector<int> dist(n, INT_MAX);
deque<int> dq;
dist[start] = 0;
dq.push_back(start);
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0)
dq.push_front(v);
else
dq.push_back(v);
}
}
}
return dist;
}
Complexity
- Time: O(V + E) -- same as BFS!
- Space: O(V)
When to Use
- Grid problems where some moves are "free" (e.g., moving along roads = 0, through fields = 1)
- Graphs where you can transform weights to 0/1
- Problems where Dijkstra's O((V+E) log V) is too slow
3. Dijkstra's Algorithm -- Non-Negative Weights
The Core Insight
Greedy choice: always process the unvisited node with the smallest known distance. Once a node is processed ("finalized"), its distance is optimal and will never change.
Why? If all edges are non-negative, any path to an unprocessed node must pass through nodes with distance >= current minimum. So we can't find a shorter path later.
Why It Fails with Negative Edges
Dijkstra from A:
Step 1: Process A (dist=0)
Relax A->B: dist[B] = 1
Relax A->C: dist[C] = 10
PQ: {(1,B), (10,C)}
Step 2: Process B (dist=1) <-- B is "finalized" with dist=1
Relax B->D: dist[D] = 1 + (-20) = -19
PQ: {(-19,D), (10,C)}
Step 3: Process D (dist=-19)
PQ: {(10,C)}
Step 4: Process C (dist=10)
Relax C->D: dist[D] = min(-19, 10+2) = -19 <-- happens to be ok here
BUT: What if C had an edge to B with weight -100?
Then after processing C, dist[B] should be 10 + (-100) = -90.
But B was already "finalized" at dist=1!
The fundamental issue: Dijkstra assumes processed nodes are done.
Negative edges can retroactively improve already-processed nodes.
Detailed Visual Walkthrough
Adjacency list (undirected):
A: [(B,2), (C,4)]
B: [(A,2), (D,3), (E,1)]
C: [(A,4), (D,1)]
D: [(B,3), (C,1), (F,5)]
E: [(B,1), (F,6)]
F: [(D,5), (E,6)]
Dijkstra from A:
Node | A | B | C | D | E | F
------|---|---|---|---|---|---
Init | 0 | * | * | * | * | * (* = infinity)
Step 1: Extract A (dist=0) Processed: {A}
Relax A->B: dist[B] = 0+2 = 2
Relax A->C: dist[C] = 0+4 = 4
PQ: {(2,B), (4,C)}
Node | A | B | C | D | E | F
------|---|---|---|---|---|---
| 0 | 2 | 4 | * | * | *
Step 2: Extract B (dist=2) Processed: {A, B}
Relax B->A: skip (A processed)
Relax B->D: dist[D] = 2+3 = 5
Relax B->E: dist[E] = 2+1 = 3
PQ: {(3,E), (4,C), (5,D)}
Node | A | B | C | D | E | F
------|---|---|---|---|---|---
| 0 | 2 | 4 | 5 | 3 | *
Step 3: Extract E (dist=3) Processed: {A, B, E}
Relax E->B: skip (B processed)
Relax E->F: dist[F] = 3+6 = 9
PQ: {(4,C), (5,D), (9,F)}
Node | A | B | C | D | E | F
------|---|---|---|---|---|---
| 0 | 2 | 4 | 5 | 3 | 9
Step 4: Extract C (dist=4) Processed: {A, B, E, C}
Relax C->A: skip (A processed)
Relax C->D: dist[D] = min(5, 4+1) = 5 (no improvement)
PQ: {(5,D), (9,F)}
Node | A | B | C | D | E | F
------|---|---|---|---|---|---
| 0 | 2 | 4 | 5 | 3 | 9
Step 5: Extract D (dist=5) Processed: {A, B, E, C, D}
Relax D->B: skip
Relax D->C: skip
Relax D->F: dist[F] = min(9, 5+5) = 9 (no improvement)
PQ: {(9,F)}
Step 6: Extract F (dist=9) Processed: {A, B, E, C, D, F}
All neighbors processed. Done!
Final distances: A=0, B=2, C=4, D=5, E=3, F=9
Implementation with Priority Queue (Lazy Deletion)
CPP
#include <bits/stdc++.h>
using namespace std;
vector<long long> dijkstra(int start, vector<vector<pair<int,int>>>& adj, int n) {
const long long INF = 1e18;
vector<long long> dist(n, INF);
// Min-heap: (distance, node)
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
// CRITICAL: skip outdated entries (lazy deletion)
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;
}
Why "lazy deletion"? We may push multiple entries for the same node into the PQ
as we discover shorter paths. Instead of decreasing the key (which std::priority_queue
doesn't support), we just push a new entry and skip outdated ones when we pop them.
Implementation with Path Reconstruction
CPP
pair<vector<long long>, vector<int>> dijkstraWithPath(
int start, vector<vector<pair<int,int>>>& adj, int n
) {
const long long INF = 1e18;
vector<long long> dist(n, INF);
vector<int> parent(n, -1);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
dist[start] = 0;
pq.push({0, start});
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;
parent[v] = u;
pq.push({dist[v], v});
}
}
}
return {dist, parent};
}
vector<int> getPath(int target, vector<int>& parent) {
vector<int> path;
for (int v = target; v != -1; v = parent[v])
path.push_back(v);
reverse(path.begin(), path.end());
return path;
}
Dense Graph Dijkstra (O(V^2), no heap)
When E is close to V^2, the heap-based Dijkstra has overhead. Use simple array scan:
CPP
vector<long long> dijkstraDense(int start, vector<vector<pair<int,int>>>& adj, int n) {
const long long INF = 1e18;
vector<long long> dist(n, INF);
vector<bool> processed(n, false);
dist[start] = 0;
for (int i = 0; i < n; i++) {
// Find unprocessed node with minimum distance
int u = -1;
for (int j = 0; j < n; j++) {
if (!processed[j] && (u == -1 || dist[j] < dist[u]))
u = j;
}
if (dist[u] == INF) break; // remaining nodes unreachable
processed[u] = true;
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
return dist;
}
Complexity Analysis
Common Pitfalls
- Using
intwhen you needlong long: If V=200000 and W=10^9, max distance can be ~2*10^14. - Not skipping outdated PQ entries: Forgetting
if (d > dist[u]) continue;leads to TLE. - Using Dijkstra with negative edges: Gives wrong answers silently!
- Adjacency list with wrong types: Make sure
{dist[v], v}matches PQ type.
4. Bellman-Ford Algorithm -- Handles Negative Edges
The Core Idea
Instead of the greedy approach (Dijkstra), relax all edges repeatedly.
Why V-1 iterations? The shortest path from source to any vertex has at most V-1 edges (since a simple path visits at most V vertices). In iteration i, we guarantee that all shortest paths using at most i edges are found correctly.
Intuition with layers:
After iteration 1: Correct distances for paths with <= 1 edge
After iteration 2: Correct distances for paths with <= 2 edges
...
After iteration V-1: Correct distances for paths with <= V-1 edges = ALL shortest paths
If iteration V still improves something -> negative cycle exists!
Detailed Visual Walkthrough
Edges: (A,B,-1), (A,D,2), (B,C,4), (D,E,3), (E,C,-3)
V = 5, so we do at most 4 iterations.
Initial: dist = [0, INF, INF, INF, INF]
A B C D E
Iteration 1 (relax all edges):
(A,B,-1): dist[B] = min(INF, 0+(-1)) = -1 UPDATED
(A,D, 2): dist[D] = min(INF, 0+2) = 2 UPDATED
(B,C, 4): dist[C] = min(INF, -1+4) = 3 UPDATED
(D,E, 3): dist[E] = min(INF, 2+3) = 5 UPDATED
(E,C,-3): dist[C] = min(3, 5+(-3)) = 2 UPDATED
dist = [0, -1, 2, 2, 5]
Iteration 2 (relax all edges):
(A,B,-1): dist[B] = min(-1, 0+(-1)) = -1 no change
(A,D, 2): dist[D] = min(2, 0+2) = 2 no change
(B,C, 4): dist[C] = min(2, -1+4) = 2 no change
(D,E, 3): dist[E] = min(5, 2+3) = 5 no change
(E,C,-3): dist[C] = min(2, 5+(-3)) = 2 no change
No updates! Early termination.
Final: A=0, B=-1, C=2, D=2, E=5
Shortest paths:
A -> A: 0
A -> B: -1 (A -> B, weight -1)
A -> C: 2 (A -> D -> E -> C, weight 2+3+(-3) = 2)
A -> D: 2 (A -> D, weight 2)
A -> E: 5 (A -> D -> E, weight 2+3 = 5)
Negative Cycle Detection -- Deep Dive
What is a negative cycle? A cycle whose total edge weight is negative.
Each time we go around, distance decreases by 5.
After V-1 iterations of Bellman-Ford, if we can STILL relax an edge,
it means some path keeps getting shorter -> negative cycle!
To FIND the actual cycle:
1. Run V iterations (one extra)
2. In the Vth iteration, if edge (u,v) is relaxed, v is affected by a negative cycle
3. Trace back parent pointers V times from v to find a node definitely in the cycle
4. Follow parent pointers from that node back to itself
Implementation
CPP
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v;
long long w;
};
// Returns shortest distances. Throws if negative cycle reachable from start.
vector<long long> bellmanFord(int start, int n, vector<Edge>& edges) {
const long long INF = 1e18;
vector<long long> dist(n, INF);
dist[start] = 0;
// Relax all edges V-1 times
for (int i = 0; i < n - 1; i++) {
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: no more improvements
}
// Vth iteration: check for negative cycles
for (auto& [u, v, w] : edges) {
if (dist[u] != INF && dist[u] + w < dist[v]) {
throw runtime_error("Negative cycle reachable from source");
}
}
return dist;
}
Finding the Actual Negative Cycle
CPP
// Returns one negative cycle as a vector of vertices, or empty if none exists.
vector<int> findNegativeCycle(int n, vector<Edge>& edges) {
const long long INF = 1e18;
vector<long long> dist(n, 0); // Initialize all to 0 to detect any cycle
vector<int> parent(n, -1);
int cycleNode = -1;
for (int i = 0; i < n; i++) {
cycleNode = -1;
for (auto& [u, v, w] : edges) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
parent[v] = u;
cycleNode = v;
}
}
}
if (cycleNode == -1) return {}; // no negative cycle
// Go back V times to ensure we're in the cycle
int v = cycleNode;
for (int i = 0; i < n; i++)
v = parent[v];
// Now v is definitely in the cycle. Trace back to find it.
vector<int> cycle;
int u = v;
do {
cycle.push_back(u);
u = parent[u];
} while (u != v);
cycle.push_back(v);
reverse(cycle.begin(), cycle.end());
return cycle;
}
Complexity
- Time: O(V * E) -- V iterations, each scanning all E edges
- Space: O(V + E)
- Early termination helps in practice but worst case is still O(VE)
5. SPFA -- Shortest Path Faster Algorithm
The Idea
SPFA is an optimization of Bellman-Ford. Instead of relaxing ALL edges in each iteration, only relax edges from nodes whose distance was recently updated (because only those can propagate improvements).
Key insight: If dist[u] didn't change, relaxing edges from u won't help. Use a queue to track which nodes need processing.
Bellman-Ford: SPFA:
for V-1 iterations: queue = {start}
for ALL edges: while queue not empty:
relax(u, v, w) u = queue.front()
for edges from u:
if relax(u, v, w):
if v not in queue:
queue.push(v)
Average case: much faster
Worst case: still O(VE) -- can be constructed adversarially!
Negative Cycle Detection in SPFA
If a node enters the queue V or more times, a negative cycle exists (it keeps getting shorter indefinitely).
Implementation
CPP
vector<long long> spfa(int start, vector<vector<pair<int,int>>>& adj, int n) {
const long long INF = 1e18;
vector<long long> dist(n, INF);
vector<bool> inQueue(n, false);
vector<int> cnt(n, 0); // number of times each node enters the queue
queue<int> q;
dist[start] = 0;
q.push(start);
inQueue[start] = true;
cnt[start] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
inQueue[u] = false;
for (auto [v, w] : 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) {
// Negative cycle detected!
return {}; // or throw
}
}
}
}
}
return dist;
}
SPFA with SLF (Shortest Label First) Optimization
CPP
// Use deque instead of queue. If new node's dist < front's dist, push to front.
vector<long long> spfaSLF(int start, vector<vector<pair<int,int>>>& adj, int n) {
const long long INF = 1e18;
vector<long long> dist(n, INF);
vector<bool> inQueue(n, false);
deque<int> dq;
dist[start] = 0;
dq.push_back(start);
inQueue[start] = true;
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
inQueue[u] = false;
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (!inQueue[v]) {
// SLF: if dist[v] < dist[front], push to front
if (!dq.empty() && dist[v] < dist[dq.front()])
dq.push_front(v);
else
dq.push_back(v);
inQueue[v] = true;
}
}
}
}
return dist;
}
When to Use SPFA vs Bellman-Ford
- SPFA: Faster in practice for most graphs. Use when you have an adjacency list.
- Bellman-Ford: Simpler, predictable O(VE). Use when you have an edge list.
- Warning: Some competitive programming problems are specifically designed to make SPFA slow. If TLE, switch to Dijkstra (if applicable) or standard Bellman-Ford.
6. DAG Shortest Path -- Topological Sort + Relaxation
The Insight
In a DAG, we can process vertices in topological order. When we process vertex u, all vertices that have edges to u have already been processed. So dist[u] is already finalized -- we can relax all edges from u.
This gives us O(V + E) shortest paths even with negative edges!
Why topological order works:
Topological order: A, B, C, D, E, F
When we process C, all predecessors of C (A, B) are done.
So dist[C] = min over all predecessors (dist[pred] + weight(pred, C))
This is already computed because predecessors come first in topo order!
It's essentially DP on a DAG.
Visual Walkthrough
Topological order: A, B, C, D, E (or A, C, B, D, E)
Processing in order A, B, C, D, E:
Process A (dist=0):
Relax A->B: dist[B] = 3
Relax A->C: dist[C] = -2
Process B (dist=3):
Relax B->D: dist[D] = 3+4 = 7
Relax B->E: dist[E] = 3+2 = 5
Process C (dist=-2):
Relax C->D: dist[D] = min(7, -2+5) = 3
Process D (dist=3):
Relax D->E: dist[E] = min(5, 3+1) = 4
Process E (dist=4): no outgoing edges
Final: A=0, B=3, C=-2, D=3, E=4
Best path to E: A -> C -> D -> E (weight -2+5+1 = 4)
Implementation
CPP
#include <bits/stdc++.h>
using namespace std;
// Topological sort using Kahn's algorithm (BFS-based)
vector<int> topologicalSort(vector<vector<pair<int,int>>>& adj, int n) {
vector<int> indegree(n, 0);
for (int u = 0; u < n; u++)
for (auto [v, w] : adj[u])
indegree[v]++;
queue<int> q;
for (int i = 0; i < n; i++)
if (indegree[i] == 0)
q.push(i);
vector<int> topo;
while (!q.empty()) {
int u = q.front(); q.pop();
topo.push_back(u);
for (auto [v, w] : adj[u])
if (--indegree[v] == 0)
q.push(v);
}
return topo;
}
vector<long long> dagShortestPath(int start, vector<vector<pair<int,int>>>& adj, int n) {
const long long INF = 1e18;
vector<int> topo = topologicalSort(adj, n);
vector<long long> dist(n, INF);
dist[start] = 0;
for (int u : topo) {
if (dist[u] == INF) continue; // unreachable from start
for (auto [v, w] : adj[u]) {
dist[v] = min(dist[v], dist[u] + w);
}
}
return dist;
}
Longest Path in a DAG
Just negate all weights and find shortest path, or change min to max:
CPP
vector<long long> dagLongestPath(int start, vector<vector<pair<int,int>>>& adj, int n) {
const long long NEG_INF = -1e18;
vector<int> topo = topologicalSort(adj, n);
vector<long long> dist(n, NEG_INF);
dist[start] = 0;
for (int u : topo) {
if (dist[u] == NEG_INF) continue;
for (auto [v, w] : adj[u]) {
dist[v] = max(dist[v], dist[u] + w);
}
}
return dist;
}
Applications
- Critical Path Method (CPM): Longest path in project scheduling DAG
- DP on DAGs: Many DP problems are actually shortest/longest path on implicit DAGs
- Number of shortest paths in DAG: Count paths that achieve the minimum distance
Complexity
- Time: O(V + E) -- topological sort is O(V+E), relaxation is O(V+E)
- Space: O(V)
7. Floyd-Warshall -- All Pairs Shortest Path
The Core Idea
Dynamic programming over intermediate vertices:
dp[k][i][j] = shortest path from i to j using only vertices {0, 1, ..., k-1}
as intermediate nodes
Base case:
dp[0][i][j] = weight(i, j) if edge exists
= 0 if i == j
= INF otherwise
Transition:
dp[k][i][j] = min(dp[k-1][i][j], // don't use vertex k-1
dp[k-1][i][k-1] + dp[k-1][k-1][j]) // use vertex k-1
Since dp[k] only depends on dp[k-1], we can use a single 2D array!
Visual Walkthrough
Weight matrix (INF where no edge):
0 1 2 3
0 [ 0 2 INF INF ]
1 [ INF 0 INF 3 ]
2 [ INF 1 0 INF ]
3 [ INF INF 7 0 ]
=== k = 0 (intermediate: vertex 0) ===
For all (i,j): dist[i][j] = min(dist[i][j], dist[i][0] + dist[0][j])
Only vertex 0 has finite outgoing paths from it.
Check: can any path be shortened by going through 0?
dist[2][1] via 0: dist[2][0] + dist[0][1] = INF + 2 = INF (no improvement)
dist[3][1] via 0: dist[3][0] + dist[0][1] = INF + 2 = INF (no improvement)
No changes.
0 1 2 3
0 [ 0 2 INF INF ]
1 [ INF 0 INF 3 ]
2 [ INF 1 0 INF ]
3 [ INF INF 7 0 ]
=== k = 1 (intermediates: {0, 1}) ===
For all (i,j): dist[i][j] = min(dist[i][j], dist[i][1] + dist[1][j])
dist[0][3] via 1: dist[0][1] + dist[1][3] = 2 + 3 = 5 < INF UPDATED!
dist[2][3] via 1: dist[2][1] + dist[1][3] = 1 + 3 = 4 < INF UPDATED!
dist[2][0] via 1: dist[2][1] + dist[1][0] = 1 + INF = INF no change
0 1 2 3
0 [ 0 2 INF 5 ]
1 [ INF 0 INF 3 ]
2 [ INF 1 0 4 ]
3 [ INF INF 7 0 ]
=== k = 2 (intermediates: {0, 1, 2}) ===
For all (i,j): dist[i][j] = min(dist[i][j], dist[i][2] + dist[2][j])
dist[0][1] via 2: dist[0][2] + dist[2][1] = INF + 1 = INF no change
dist[3][1] via 2: dist[3][2] + dist[2][1] = 7 + 1 = 8 < INF UPDATED!
dist[3][3] via 2: dist[3][2] + dist[2][3] = 7 + 4 = 11 > 0 no change
dist[3][0] via 2: dist[3][2] + dist[2][0] = 7 + INF = INF no change
0 1 2 3
0 [ 0 2 INF 5 ]
1 [ INF 0 INF 3 ]
2 [ INF 1 0 4 ]
3 [ INF 8 7 0 ]
=== k = 3 (intermediates: {0, 1, 2, 3}) ===
For all (i,j): dist[i][j] = min(dist[i][j], dist[i][3] + dist[3][j])
dist[0][2] via 3: dist[0][3] + dist[3][2] = 5 + 7 = 12 < INF UPDATED!
dist[0][1] via 3: dist[0][3] + dist[3][1] = 5 + 8 = 13 > 2 no change
dist[1][2] via 3: dist[1][3] + dist[3][2] = 3 + 7 = 10 < INF UPDATED!
dist[1][1] via 3: dist[1][3] + dist[3][1] = 3 + 8 = 11 > 0 no change
dist[2][2] via 3: dist[2][3] + dist[3][2] = 4 + 7 = 11 > 0 no change
Final result:
0 1 2 3
0 [ 0 2 12 5 ]
1 [ INF 0 10 3 ]
2 [ INF 1 0 4 ]
3 [ INF 8 7 0 ]
Verify: 0->2 = 0->1->3->2 = 2+3+7 = 12 (correct!)
1->2 = 1->3->2 = 3+7 = 10 (correct!)
Implementation
CPP
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
void floydWarshall(vector<vector<long long>>& dist, int n) {
// dist[i][j] should be initialized:
// 0 if i == j
// w(i,j) if edge exists
// INF otherwise
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; 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]);
}
}
}
}
}
// Check for negative cycles
bool hasNegativeCycle(vector<vector<long long>>& dist, int n) {
for (int i = 0; i < n; i++)
if (dist[i][i] < 0)
return true;
return false;
}
Path Reconstruction in Floyd-Warshall
CPP
vector<vector<int>> next_node; // next_node[i][j] = next node on shortest path from i to j
void floydWarshallWithPath(vector<vector<long long>>& dist, int n) {
next_node.assign(n, vector<int>(n, -1));
// Initialize: if edge i->j exists, next_node[i][j] = j
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][j] < INF && i != j)
next_node[i][j] = j;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][k] < INF && dist[k][j] < INF &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
next_node[i][j] = next_node[i][k];
}
}
vector<int> getPath(int u, int v) {
if (next_node[u][v] == -1) return {}; // no path
vector<int> path = {u};
while (u != v) {
u = next_node[u][v];
path.push_back(u);
}
return path;
}
Transitive Closure (Reachability)
A special case of Floyd-Warshall: can i reach j?
CPP
void transitiveClosure(vector<vector<bool>>& reach, int n) {
// reach[i][j] = true if edge i->j exists, or i==j
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
}
Minimax Path (Widest Path / Bottleneck Shortest Path)
CPP
// dist[i][j] = min over all paths from i to j of (max edge weight on path)
void minimaxPath(vector<vector<long long>>& dist, int n) {
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]));
}
Complexity
- Time: O(V^3)
- Space: O(V^2)
- Practical limit: V <= 400-500 (depending on time limit)
8. Johnson's Algorithm -- All Pairs for Sparse Graphs
The Problem
Floyd-Warshall is O(V^3). For sparse graphs (E << V^2), this is wasteful. Can we do better?
Idea: Run Dijkstra from every vertex -> O(V(V+E) log V). But Dijkstra needs non-negative edges!
Johnson's trick: Reweight edges to eliminate negative weights while preserving shortest paths.
The Reweighting Technique
1. Add a virtual source vertex S connected to all vertices with weight 0.
2. Run Bellman-Ford from S to get h[v] = shortest distance from S to v.
3. Reweight each edge (u,v) with weight w:
w'(u, v) = w(u, v) + h[u] - h[v]
4. Claim: w'(u,v) >= 0 for all edges!
Proof: Since h[v] <= h[u] + w(u,v) (triangle inequality from Bellman-Ford),
w(u,v) + h[u] - h[v] >= 0
5. Claim: shortest paths are preserved!
Proof: For any path P from a to b:
w'(P) = sum of w'(u,v) for edges in P
= sum of (w(u,v) + h[u] - h[v])
= w(P) + h[a] - h[b] (telescoping!)
Since h[a] - h[b] is constant for fixed a,b, the path that
minimizes w(P) also minimizes w'(P).
6. After reweighting, run Dijkstra from every vertex.
7. Recover true distances: dist(u,v) = dist'(u,v) - h[u] + h[v]
Visual Example
Step 1: Add virtual source S with 0-weight edges to all
S --(0)--> A, S --(0)--> B, S --(0)--> C, S --(0)--> D
Step 2: Bellman-Ford from S:
h[A] = 0, h[B] = 0, h[C] = -3, h[D] = 0
(shortest paths: S->A=0, S->B=0, S->A->C=-3, S->D=0)
Wait, h[B] could be 2 via S->A->B.
h[A] = 0, h[B] = min(0, 0+2) = 0
h[C] = min(0, 0+(-3)) = -3
h[D] = min(0, 0+4, -3+1) = -2
Actually: h[D] = min(0, h[B]+4, h[C]+1) = min(0, 4, -2) = -2
Step 3: Reweight:
w'(A,B) = 2 + h[A] - h[B] = 2 + 0 - 0 = 2
w'(A,C) = -3 + h[A] - h[C] = -3 + 0 - (-3) = 0
w'(C,D) = 1 + h[C] - h[D] = 1 + (-3) - (-2) = 0
w'(B,D) = 4 + h[B] - h[D] = 4 + 0 - (-2) = 6
All reweighted edges are >= 0! Now run Dijkstra from each vertex.
Implementation
CPP
#include <bits/stdc++.h>
using namespace std;
vector<vector<long long>> johnsons(int n, vector<vector<pair<int,int>>>& adj) {
const long long INF = 1e18;
// Step 1: Add virtual source (node n) with 0-weight edges to all
vector<Edge> edges;
for (int u = 0; u < n; u++) {
edges.push_back({n, u, 0}); // virtual source -> u
for (auto [v, w] : adj[u])
edges.push_back({u, v, w});
}
// Step 2: Bellman-Ford from virtual source
vector<long long> h(n + 1, INF);
h[n] = 0;
for (int i = 0; i < n; i++) { // n iterations (n+1 vertices - 1)
for (auto& [u, v, w] : edges) {
if (h[u] != INF && h[u] + w < h[v]) {
h[v] = h[u] + w;
}
}
}
// Check for negative cycle
for (auto& [u, v, w] : edges)
if (h[u] != INF && h[u] + w < h[v])
return {}; // negative cycle exists
// Step 3: Reweight
vector<vector<pair<int,long long>>> adjNew(n);
for (int u = 0; u < n; u++)
for (auto [v, w] : adj[u])
adjNew[u].push_back({v, w + h[u] - h[v]});
// Step 4: Run Dijkstra from each vertex
vector<vector<long long>> dist(n, vector<long long>(n, INF));
for (int src = 0; src < n; src++) {
// Dijkstra from src on reweighted graph
vector<long long> d(n, INF);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
d[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [dd, u] = pq.top(); pq.pop();
if (dd > d[u]) continue;
for (auto [v, w] : adjNew[u]) {
if (d[u] + w < d[v]) {
d[v] = d[u] + w;
pq.push({d[v], v});
}
}
}
// Step 5: Recover true distances
for (int v = 0; v < n; v++) {
if (d[v] < INF)
dist[src][v] = d[v] - h[src] + h[v];
}
}
return dist;
}
Complexity
- Bellman-Ford: O(VE)
- V Dijkstra runs: O(V * (V+E) log V)
- Total: O(V^2 log V + VE)
For sparse graphs (E ~ V), this is O(V^2 log V) vs Floyd-Warshall's O(V^3).
9. Shortest Paths on Grids
Grids are the most common graph type in competitive programming problems. The graph is implicit -- cells are nodes, adjacent cells have edges.
BFS on Grid (Unweighted)
CPP
int shortestPathGrid(vector<vector<int>>& grid, pair<int,int> start, pair<int,int> end) {
int m = grid.size(), n = grid[0].size();
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
vector<vector<int>> dist(m, vector<int>(n, -1));
queue<pair<int,int>> q;
dist[start.first][start.second] = 0;
q.push(start);
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
if (x == end.first && y == end.second)
return dist[x][y];
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
grid[nx][ny] != 1 && dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
}
return -1; // unreachable
}
Dijkstra on Grid (Weighted)
CPP
int shortestPathWeightedGrid(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;
dist[0][0] = grid[0][0];
pq.push({grid[0][0], 0, 0});
while (!pq.empty()) {
auto [d, x, y] = pq.top(); pq.pop();
if (d > dist[x][y]) continue;
if (x == m-1 && y == n-1) return d;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int nd = d + grid[nx][ny];
if (nd < dist[nx][ny]) {
dist[nx][ny] = nd;
pq.push({nd, nx, ny});
}
}
}
}
return dist[m-1][n-1];
}
Multi-Source BFS
Start BFS from multiple sources simultaneously (e.g., find distance from each cell to the nearest source).
CPP
// dist[i][j] = distance from (i,j) to nearest source
vector<vector<int>> multiSourceBFS(vector<vector<int>>& grid,
vector<pair<int,int>>& sources) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dist(m, vector<int>(n, -1));
queue<pair<int,int>> q;
for (auto [x, y] : sources) {
dist[x][y] = 0;
q.push({x, y});
}
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
grid[nx][ny] != 1 && dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
}
return dist;
}
10. Advanced Techniques and Variants
Shortest Path with State (Layered Graph / State-Space BFS)
Many problems require tracking additional state beyond just the current node. Model this as a multi-dimensional state space.
Example: Shortest path with at most K stops
State: (node, stops_used)
Graph: (V * K) nodes
Instead of dist[v], use dist[v][k] = shortest path to v using exactly k stops.
CPP
// Shortest path from src to dst with at most K edges
// (Bellman-Ford variant)
int shortestPathKEdges(int n, vector<Edge>& edges, int src, int dst, int K) {
const int INF = 1e9;
vector<int> dist(n, INF);
dist[src] = 0;
for (int i = 0; i < K; i++) {
vector<int> newDist = dist; // copy! Important!
for (auto& [u, v, w] : edges) {
if (dist[u] != INF)
newDist[v] = min(newDist[v], dist[u] + w);
}
dist = newDist;
}
return dist[dst] == INF ? -1 : dist[dst];
}
Dial's Algorithm (Bucket Queue Dijkstra)
When edge weights are small integers in [0, C], use an array of buckets:
CPP
vector<long long> dialDijkstra(int start, vector<vector<pair<int,int>>>& adj, int n, int maxW) {
const long long INF = 1e18;
vector<long long> dist(n, INF);
vector<vector<int>> buckets(n * maxW + 1);
dist[start] = 0;
buckets[0].push_back(start);
int idx = 0;
for (int d = 0; d < (int)buckets.size(); d++) {
for (int i = 0; i < (int)buckets[d].size(); i++) {
int u = buckets[d][i];
if (dist[u] != d) continue; // outdated
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
buckets[dist[v]].push_back(v);
}
}
}
}
return dist;
}
Complexity: O(V + E + maxDist) where maxDist = V * maxW.
Bidirectional Dijkstra
Run Dijkstra from both source and target. Stop when they "meet."
Forward search: S -> ... -> meeting point
Backward search: T -> ... -> meeting point
S ------> <------- T
expanding expanding
When we process a node that's been processed by the other search,
we've found a candidate shortest path.
Caution: The meeting point might NOT be on the actual shortest path!
We need to check: for all edges (u,v), min(distF[u] + w(u,v) + distB[v])
CPP
long long bidirectionalDijkstra(int src, int dst,
vector<vector<pair<int,int>>>& adj,
vector<vector<pair<int,int>>>& radj, int n) {
const long long INF = 1e18;
vector<long long> distF(n, INF), distB(n, INF);
vector<bool> procF(n, false), procB(n, false);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pqF, pqB;
distF[src] = 0; pqF.push({0, src});
distB[dst] = 0; pqB.push({0, dst});
long long ans = INF;
while (!pqF.empty() || !pqB.empty()) {
// Forward step
if (!pqF.empty()) {
auto [d, u] = pqF.top(); pqF.pop();
if (d <= ans) {
procF[u] = true;
if (procB[u]) ans = min(ans, distF[u] + distB[u]);
for (auto [v, w] : adj[u]) {
if (distF[u] + w < distF[v]) {
distF[v] = distF[u] + w;
pqF.push({distF[v], v});
}
}
}
}
// Backward step
if (!pqB.empty()) {
auto [d, u] = pqB.top(); pqB.pop();
if (d <= ans) {
procB[u] = true;
if (procF[u]) ans = min(ans, distF[u] + distB[u]);
for (auto [v, w] : radj[u]) {
if (distB[u] + w < distB[v]) {
distB[v] = distB[u] + w;
pqB.push({distB[v], v});
}
}
}
}
// Termination: if both PQs' top > ans/2
if (!pqF.empty() && !pqB.empty() &&
pqF.top().first + pqB.top().first >= ans)
break;
}
return ans;
}
Number of Shortest Paths
CPP
pair<vector<long long>, vector<long long>> countShortestPaths(
int start, vector<vector<pair<int,int>>>& adj, int n, int MOD
) {
const long long INF = 1e18;
vector<long long> dist(n, INF), cnt(n, 0);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
dist[start] = 0;
cnt[start] = 1;
pq.push({0, start});
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;
cnt[v] = cnt[u];
pq.push({dist[v], v});
} else if (dist[u] + w == dist[v]) {
cnt[v] = (cnt[v] + cnt[u]) % MOD;
}
}
}
return {dist, cnt};
}
Summary Decision Tree
Classic Problems with Solutions
Problem 1: Network Delay Time (LeetCode 743)
Problem: You are given a network of n nodes labeled 1 to n. Given times[i] = (ui, vi, wi)
representing a directed edge with travel time wi, and a source node k, return the minimum
time for all nodes to receive the signal. Return -1 if not all nodes are reachable.
Approach: Single-source shortest path, non-negative weights -> Dijkstra. The answer is the maximum shortest distance.
CPP
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<pair<int,int>>> adj(n + 1);
for (auto& t : times)
adj[t[0]].push_back({t[1], t[2]});
const int INF = 1e9;
vector<int> dist(n + 1, INF);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
dist[k] = 0;
pq.push({0, k});
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});
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] == INF) return -1;
ans = max(ans, dist[i]);
}
return ans;
}
};
Problem 2: Cheapest Flights Within K Stops (LeetCode 787)
Problem: Find the cheapest flight from src to dst with at most K stops (K+1 edges).
Approach: Modified Bellman-Ford with exactly K+1 iterations. At each iteration, relax all edges using distances from the PREVIOUS iteration (not current -- to avoid using more edges than allowed).
CPP
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
const int INF = 1e9;
vector<int> dist(n, INF);
dist[src] = 0;
// k stops = k+1 edges, so k+1 iterations
for (int i = 0; i <= k; i++) {
vector<int> newDist = dist; // COPY! This ensures we use at most i+1 edges
for (auto& f : flights) {
int u = f[0], v = f[1], w = f[2];
if (dist[u] != INF) {
newDist[v] = min(newDist[v], dist[u] + w);
}
}
dist = newDist;
}
return dist[dst] == INF ? -1 : dist[dst];
}
};
Why copy? If we update dist in place, a chain A->B->C->D could propagate in a
single iteration (using 3 edges when we only wanted 1). Copying ensures each iteration
adds at most 1 edge.
Problem 3: Path with Maximum Probability (LeetCode 1514)
Problem: Find the path with maximum probability from start to end.
Approach: Modified Dijkstra. Instead of minimizing sum, maximize product. Use max-heap instead of min-heap.
CPP
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb,
int start_node, int end_node) {
vector<vector<pair<int,double>>> adj(n);
for (int i = 0; i < (int)edges.size(); i++) {
adj[edges[i][0]].push_back({edges[i][1], succProb[i]});
adj[edges[i][1]].push_back({edges[i][0], succProb[i]});
}
vector<double> prob(n, 0.0);
priority_queue<pair<double,int>> pq; // max-heap
prob[start_node] = 1.0;
pq.push({1.0, start_node});
while (!pq.empty()) {
auto [p, u] = pq.top(); pq.pop();
if (p < prob[u]) continue; // outdated
if (u == end_node) return p;
for (auto [v, w] : adj[u]) {
if (prob[u] * w > prob[v]) {
prob[v] = prob[u] * w;
pq.push({prob[v], v});
}
}
}
return 0.0;
}
};
Problem 4: Find the City With the Smallest Number of Neighbors (LeetCode 1334)
Problem: Given n cities and weighted edges, find the city with the smallest number of cities reachable within distanceThreshold. Return the city with the greatest index if tied.
Approach: All-pairs shortest path. V <= 100, so Floyd-Warshall is perfect.
CPP
class Solution {
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
const int INF = 1e9;
vector<vector<int>> dist(n, vector<int>(n, INF));
for (int i = 0; i < n; i++) dist[i][i] = 0;
for (auto& e : edges) {
dist[e[0]][e[1]] = e[2];
dist[e[1]][e[0]] = e[2];
}
// Floyd-Warshall
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; 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 bestCity = -1, bestCount = n + 1;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++)
if (i != j && dist[i][j] <= distanceThreshold)
count++;
if (count <= bestCount) { // <= to prefer greatest index
bestCount = count;
bestCity = i;
}
}
return bestCity;
}
};
Problem 5: Shortest Path with Alternating Colors (LeetCode 1129)
Problem: Graph with red and blue edges. Find shortest path from 0 to each node using alternating colors.
Approach: BFS with state = (node, last_color). This is a state-space BFS.
CPP
class Solution {
public:
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges,
vector<vector<int>>& blueEdges) {
// adj[node][color] = list of neighbors
// color: 0 = red, 1 = blue
vector<vector<vector<int>>> adj(n, vector<vector<int>>(2));
for (auto& e : redEdges) adj[e[0]][0].push_back(e[1]);
for (auto& e : blueEdges) adj[e[0]][1].push_back(e[1]);
// dist[node][last_color]
vector<vector<int>> dist(n, vector<int>(2, -1));
queue<tuple<int,int,int>> q; // (node, color, distance)
// Start from 0 with either color
q.push({0, 0, 0}); dist[0][0] = 0;
q.push({0, 1, 0}); dist[0][1] = 0;
while (!q.empty()) {
auto [u, c, d] = q.front(); q.pop();
// Next edge must be opposite color
int nc = 1 - c;
for (int v : adj[u][nc]) {
if (dist[v][nc] == -1) {
dist[v][nc] = d + 1;
q.push({v, nc, d + 1});
}
}
}
vector<int> ans(n);
for (int i = 0; i < n; i++) {
if (dist[i][0] == -1 && dist[i][1] == -1)
ans[i] = -1;
else if (dist[i][0] == -1)
ans[i] = dist[i][1];
else if (dist[i][1] == -1)
ans[i] = dist[i][0];
else
ans[i] = min(dist[i][0], dist[i][1]);
}
return ans;
}
};