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.

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);
    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();
        
        if (d > dist[u]) continue;  // Skip outdated entries
        
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

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. Prefer Dijkstra for non-negative weights.

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.

Mistake 2: Not handling disconnected components If destination is unreachable, return -1, not INF.

Mistake 3: Using Dijkstra with negative weights Dijkstra does NOT work with negative edges. Use Bellman-Ford.

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

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

​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