Shortest Path Algorithms

Algorithm Selection Guide

Algorithm	Graph Type	Weights	Complexity	Use Case
BFS	Any	Unweighted	O(V + E)	Equal edge weights
0-1 BFS	Any	0 or 1	O(V + E)	Binary weights
Dijkstra	Any	Non-negative	O(E log V)	General shortest path
Bellman-Ford	Any	Any	O(VE)	Negative weights, cycle detection
Floyd-Warshall	Dense	Any	O(V³)	All-pairs shortest path

Pattern Recognition Signals:

“Shortest path” with all weights = 1 → BFS
“Minimum cost path” with non-negative weights → Dijkstra
“Negative weights” or “detect negative cycle” → Bellman-Ford
“All pairs shortest path” with small n (≤400) → Floyd-Warshall
Weights are only 0 and 1 → 0-1 BFS

Dijkstra’s Algorithm

The workhorse for single-source shortest path with non-negative weights. Analogy: Imagine a fire starting at the source node and spreading through the graph. The fire reaches closer nodes first, then spreads to farther ones. The priority queue ensures we always process the closest unvisited node, just like fire always advances through the shortest fuel path first. Why it works: Dijkstra greedily finalizes the closest unvisited node. With non-negative weights, once a node is finalized, no future path through unvisited nodes could be shorter (they would have to pass through nodes that are farther away and add non-negative weight). This greedy property breaks with negative weights.

Standard Implementation

const long long INF = 1e18;

vector<long long> dijkstra(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<long long> dist(n, INF);
    // Min-heap: process closest node first. Pair is {distance, node}.
    priority_queue<pair<long long, int>, 
                   vector<pair<long long, int>>, 
                   greater<pair<long long, int>>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        // Key optimization: skip if we already found a shorter path to u.
        // Without this, complexity degrades because stale entries pile up.
        if (d > dist[u]) continue;
        
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;       // Relaxation
                pq.push({dist[v], v});        // Lazy deletion: push new entry
            }
        }
    }
    
    return dist;
}
// Time: O(E log V) with binary heap, O(E + V log V) with Fibonacci heap

Path Reconstruction

vector<int> dijkstraWithPath(int start, int end, 
                              vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    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});
            }
        }
    }
    
    // Reconstruct path
    vector<int> path;
    if (dist[end] == INF) return path;  // No path
    
    for (int cur = end; cur != -1; cur = parent[cur]) {
        path.push_back(cur);
    }
    reverse(path.begin(), path.end());
    
    return path;
}

Critical Mistake: Using int for distances With weights up to 10^9 and paths up to 10^5 edges, total distance can exceed 10^14. Use long long.

0-1 BFS

For graphs where edges have weight 0 or 1. Uses deque instead of priority queue. Why it works: With only 0 and 1 weights:

0-weight edges don’t increase distance → add to front of deque
1-weight edges increase distance by 1 → add to back of deque

This maintains the invariant that the deque is sorted by distance (like a priority queue, but O(1) instead of O(log n) per operation). When to Use:

Grid problems where moving is free but breaking walls costs 1
Graphs with binary edge weights
Faster than Dijkstra: O(V + E) vs O(E log V)

vector<int> bfs01(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    deque<int> dq;
    
    dist[start] = 0;
    dq.push_front(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);  // 0-weight: front
                } else {
                    dq.push_back(v);   // 1-weight: back
                }
            }
        }
    }
    
    return dist;
}

Classic Application: Grid with blocked cells that cost 1 to break through.

Bellman-Ford Algorithm

Handles negative edge weights and detects negative cycles. Why Dijkstra Fails with Negative Weights: Dijkstra assumes once a node is “finalized,” its distance can’t improve. With negative edges, this breaks—a longer path might become shorter later! The Insight: After at most (n-1) relaxations of all edges, shortest paths are found (if no negative cycle). Why n-1? The longest simple path has n-1 edges. Negative Cycle Detection: If any distance improves on the nth iteration, there’s a negative cycle—distances can decrease infinitely! When to Use:

Negative edge weights (Dijkstra fails)
Need to detect negative cycles
Sparse graphs with few edges

const long long INF = 1e18;

pair<vector<long long>, bool> bellmanFord(
    int start, int n, vector<tuple<int, int, int>>& edges) {
    
    vector<long long> dist(n + 1, INF);
    dist[start] = 0;
    
    // Relax all edges n-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
    }
    
    // Check for negative cycle
    bool hasNegativeCycle = false;
    for (auto [u, v, w] : edges) {
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            hasNegativeCycle = true;
            break;
        }
    }
    
    return {dist, hasNegativeCycle};
}

Finding Negative Cycle

vector<int> findNegativeCycle(int n, vector<tuple<int, int, int>>& edges) {
    vector<long long> dist(n + 1, 0);  // Start from 0, not INF
    vector<int> parent(n + 1, -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
    
    // Find a node in the cycle
    for (int i = 0; i < n; i++) {
        cycleNode = parent[cycleNode];
    }
    
    // Extract cycle
    vector<int> cycle;
    int cur = cycleNode;
    do {
        cycle.push_back(cur);
        cur = parent[cur];
    } while (cur != cycleNode);
    cycle.push_back(cycleNode);
    
    reverse(cycle.begin(), cycle.end());
    return cycle;
}

Floyd-Warshall Algorithm

Computes all-pairs shortest paths. Works with negative weights (but no negative cycles). The Idea: For each pair (i, j), try using each vertex k as an intermediate point.

dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j])

Why the loop order matters: We iterate k on the outside. After iteration k, dist[i][j] contains the shortest path using only vertices 1 to k as intermediates. Complexity: O(V³)—only use when V ≤ 400 When to Use:

Need all pairs shortest paths
Graph is dense (many edges)
V is small (≤ 400)

const long long INF = 1e18;

vector<vector<long long>> floydWarshall(int n, 
                                         vector<tuple<int, int, int>>& edges) {
    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));
    
    // Initialize
    for (int i = 1; i <= n; i++) dist[i][i] = 0;
    
    for (auto [u, v, w] : edges) {
        dist[u][v] = min(dist[u][v], (long long)w);
    }
    
    // Floyd-Warshall
    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]);
                }
            }
        }
    }
    
    return dist;
}

Detecting Negative Cycles with Floyd-Warshall

After running the algorithm, check if any dist[i][i] < 0.

SPFA (Bellman-Ford Optimization)

Shortest Path Faster Algorithm—optimized Bellman-Ford with queue.

vector<long long> spfa(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<long long> dist(n, INF);
    vector<bool> inQueue(n, false);
    queue<int> q;
    
    dist[start] = 0;
    q.push(start);
    inQueue[start] = true;
    
    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;
                }
            }
        }
    }
    
    return dist;
}

SPFA has worst-case O(VE) and can be slow on adversarial inputs. Many competitive programming judges include anti-SPFA test cases specifically to fail this algorithm. Prefer Dijkstra for non-negative weights. Only use SPFA when you need Bellman-Ford’s capabilities (negative weights) with potentially faster average performance.

Pattern 1: Multi-Source Shortest Path

Problem: Find shortest path from any of K source nodes. Solution: Add all sources to initial queue/priority queue.

vector<long long> multiSourceDijkstra(
    vector<int>& sources, vector<vector<pair<int, int>>>& adj) {
    
    int n = adj.size();
    vector<long long> dist(n, INF);
    priority_queue<pair<long long, int>, 
                   vector<pair<long long, int>>, 
                   greater<>> pq;
    
    // Add all sources
    for (int s : sources) {
        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;
}

Pattern 2: Shortest Path with Constraints

Problem: Shortest path with at most K edges, or at most K toll roads. Solution: Add state dimension.

// Shortest path with at most K edges
vector<vector<long long>> dijkstraWithK(
    int start, int K, vector<vector<pair<int, int>>>& adj) {
    
    int n = adj.size();
    // dist[u][k] = shortest path to u using exactly k edges
    vector<vector<long long>> dist(n, vector<long long>(K + 1, INF));
    priority_queue<tuple<long long, int, int>,
                   vector<tuple<long long, int, int>>,
                   greater<>> pq;
    
    dist[start][0] = 0;
    pq.push({0, start, 0});
    
    while (!pq.empty()) {
        auto [d, u, k] = pq.top();
        pq.pop();
        
        if (d > dist[u][k]) continue;
        if (k == K) continue;  // Can't use more edges
        
        for (auto [v, w] : adj[u]) {
            if (dist[u][k] + w < dist[v][k + 1]) {
                dist[v][k + 1] = dist[u][k] + w;
                pq.push({dist[v][k + 1], v, k + 1});
            }
        }
    }
    
    return dist;
}

Pattern 3: Shortest Path on DAG

Problem: Shortest path in a Directed Acyclic Graph. Solution: Topological sort + DP. O(V + E).

vector<long long> shortestPathDAG(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<int> inDegree(n, 0);
    
    for (int u = 0; u < n; u++) {
        for (auto [v, w] : adj[u]) {
            inDegree[v]++;
        }
    }
    
    // Topological sort
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) q.push(i);
    }
    
    vector<int> order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        
        for (auto [v, w] : adj[u]) {
            if (--inDegree[v] == 0) q.push(v);
        }
    }
    
    // DP
    vector<long long> dist(n, INF);
    dist[start] = 0;
    
    for (int u : order) {
        if (dist[u] == INF) continue;
        
        for (auto [v, w] : adj[u]) {
            dist[v] = min(dist[v], dist[u] + w);
        }
    }
    
    return dist;
}

Pattern 4: Meet in the Middle (Bidirectional)

Problem: Shortest path from A to B in a very large graph. Solution: Run Dijkstra from both ends.

long long bidirectionalDijkstra(
    int start, int end, vector<vector<pair<int, int>>>& adj,
    vector<vector<pair<int, int>>>& radj) {  // Reverse graph
    
    int n = adj.size();
    vector<long long> distF(n, INF), distB(n, INF);
    priority_queue<pair<long long, int>, 
                   vector<pair<long long, int>>, 
                   greater<>> pqF, pqB;
    vector<bool> doneF(n, false), doneB(n, false);
    
    distF[start] = 0;
    distB[end] = 0;
    pqF.push({0, start});
    pqB.push({0, end});
    
    long long ans = INF;
    
    while (!pqF.empty() || !pqB.empty()) {
        // Expand forward
        if (!pqF.empty()) {
            auto [d, u] = pqF.top();
            pqF.pop();
            
            if (doneF[u]) continue;
            doneF[u] = true;
            
            if (doneB[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});
                }
            }
        }
        
        // Expand backward (similar)
        // ...
    }
    
    return ans;
}

Common Mistakes

Mistake 1: Wrong INF value Use 1e18 for long long. Using INT_MAX causes overflow when adding: INT_MAX + 1 wraps to a negative number, which then appears “shorter” than real distances.

// WRONG -- overflow when checking dist[u] + w
const int INF = INT_MAX;

// CORRECT -- large enough that INF + max_edge never overflows long long
const long long INF = 1e18;

Mistake 2: Not handling disconnected components If destination is unreachable, return -1, not INF. Many problems penalize printing a huge number instead of -1 or “impossible.”

cout << (dist[target] == INF ? -1 : dist[target]) << '\n';

Mistake 3: Using Dijkstra with negative weights Dijkstra does NOT work with negative edges. Use Bellman-Ford or SPFA. Even a single negative edge can make Dijkstra produce wrong answers, because it finalizes nodes greedily under the assumption that distances only increase.

Mistake 4: Multiple edges between the same pair of nodes When reading the graph, always take the minimum weight if there are parallel edges:

adj[u][v] = min(adj[u][v], w);  // For adjacency matrix
// For adjacency list, it is fine to store all edges -- Dijkstra handles it

Practice Problems

Beginner (1000-1300)

Problem	Algorithm	Link
Shortest Routes I	Dijkstra	CSES
Shortest Routes II	Floyd-Warshall	CSES

Intermediate (1300-1600)

Problem	Pattern	Link
Flight Discount	Dijkstra + state	CSES
High Score	Negative cycle	CSES
Dijkstra?	Dijkstra	CF 20C

Advanced (1600-1900)

Problem	Pattern	Link
Cycle Finding	Bellman-Ford	CSES
Investigation	Dijkstra + counting	CSES

Key Takeaways

Dijkstra for Non-Negative

O(E log V), most common algorithm in CP.

Bellman-Ford for Negative

O(VE), detects negative cycles.

Floyd for All-Pairs

O(V³), when you need all pairs and n ≤ 400.

0-1 BFS for Binary

O(V + E), when weights are only 0 and 1.

Next Up

Chapter 15: Trees

Master tree traversals, LCA, and tree DP for hierarchical structures.

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Shortest Path Algorithms

Shortest Path Algorithms

Algorithm Selection Guide

Dijkstra’s Algorithm

Standard Implementation

Path Reconstruction

0-1 BFS

Bellman-Ford Algorithm

Finding Negative Cycle

Floyd-Warshall Algorithm

Detecting Negative Cycles with Floyd-Warshall

SPFA (Bellman-Ford Optimization)

Pattern 1: Multi-Source Shortest Path

Pattern 2: Shortest Path with Constraints

Pattern 3: Shortest Path on DAG

Pattern 4: Meet in the Middle (Bidirectional)

Common Mistakes

Practice Problems

Beginner (1000-1300)

Intermediate (1300-1600)

Advanced (1600-1900)

Key Takeaways

Dijkstra for Non-Negative

Bellman-Ford for Negative

Floyd for All-Pairs

0-1 BFS for Binary

Next Up

Chapter 15: Trees

​Shortest Path Algorithms

​Algorithm Selection Guide

​Dijkstra’s Algorithm

​Standard Implementation

​Path Reconstruction

​0-1 BFS

​Bellman-Ford Algorithm

​Finding Negative Cycle

​Floyd-Warshall Algorithm

​Detecting Negative Cycles with Floyd-Warshall

​SPFA (Bellman-Ford Optimization)

​Pattern 1: Multi-Source Shortest Path

​Pattern 2: Shortest Path with Constraints

​Pattern 3: Shortest Path on DAG

​Pattern 4: Meet in the Middle (Bidirectional)

​Common Mistakes

​Practice Problems

​Beginner (1000-1300)

​Intermediate (1300-1600)

​Advanced (1600-1900)

​Key Takeaways

Dijkstra for Non-Negative

Bellman-Ford for Negative

Floyd for All-Pairs

0-1 BFS for Binary

​Next Up

Chapter 15: Trees

Shortest Path Algorithms

Algorithm Selection Guide

Dijkstra’s Algorithm

Standard Implementation

Path Reconstruction

0-1 BFS

Bellman-Ford Algorithm

Finding Negative Cycle

Floyd-Warshall Algorithm

Detecting Negative Cycles with Floyd-Warshall

SPFA (Bellman-Ford Optimization)

Pattern 1: Multi-Source Shortest Path

Pattern 2: Shortest Path with Constraints

Pattern 3: Shortest Path on DAG

Pattern 4: Meet in the Middle (Bidirectional)

Common Mistakes

Practice Problems

Beginner (1000-1300)

Intermediate (1300-1600)

Advanced (1600-1900)

Key Takeaways

Next Up