> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Shortest Path Algorithms

> Master Dijkstra, Bellman-Ford, Floyd-Warshall, and 0-1 BFS for weighted graphs

# Shortest Path Algorithms

<img src="https://mintcdn.com/devweeekends/AEOaWh79Ur7CdHHv/images/courses/cp/shortest-path-mental-model.svg?fit=max&auto=format&n=AEOaWh79Ur7CdHHv&q=85&s=53a349fe2d1d0a2ca58f23ea6c13319a" alt="Shortest Path Algorithm Selection" width="1080" height="1080" data-path="images/courses/cp/shortest-path-mental-model.svg" />

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

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

***

## Dijkstra's Algorithm

<img src="https://mintcdn.com/devweeekends/AEOaWh79Ur7CdHHv/images/courses/cp/dijkstra-visualization.svg?fit=max&auto=format&n=AEOaWh79Ur7CdHHv&q=85&s=2ae5e2ae63d8ced3346eb03c1afb8643" alt="Dijkstra's Algorithm Visualization" width="1080" height="1080" data-path="images/courses/cp/dijkstra-visualization.svg" />

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

```cpp theme={null}
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

```cpp theme={null}
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;
}
```

<Warning>
  **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`.
</Warning>

***

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

```cpp theme={null}
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

```cpp theme={null}
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

```cpp theme={null}
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)

```cpp theme={null}
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.

```cpp theme={null}
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;
}
```

<Warning>
  **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.
</Warning>

***

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

```cpp theme={null}
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.

```cpp theme={null}
// 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).

```cpp theme={null}
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.

```cpp theme={null}
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

<Warning>
  **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.

  ```cpp theme={null}
  // 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;
  ```
</Warning>

<Warning>
  **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."

  ```cpp theme={null}
  cout << (dist[target] == INF ? -1 : dist[target]) << '\n';
  ```
</Warning>

<Warning>
  **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.
</Warning>

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

  ```cpp theme={null}
  adj[u][v] = min(adj[u][v], w);  // For adjacency matrix
  // For adjacency list, it is fine to store all edges -- Dijkstra handles it
  ```
</Warning>

***

## Practice Problems

### Beginner (1000-1300)

| Problem            | Algorithm      | Link                                         |
| ------------------ | -------------- | -------------------------------------------- |
| Shortest Routes I  | Dijkstra       | [CSES](https://cses.fi/problemset/task/1671) |
| Shortest Routes II | Floyd-Warshall | [CSES](https://cses.fi/problemset/task/1672) |

### Intermediate (1300-1600)

| Problem         | Pattern          | Link                                                     |
| --------------- | ---------------- | -------------------------------------------------------- |
| Flight Discount | Dijkstra + state | [CSES](https://cses.fi/problemset/task/1195)             |
| High Score      | Negative cycle   | [CSES](https://cses.fi/problemset/task/1673)             |
| Dijkstra?       | Dijkstra         | [CF 20C](https://codeforces.com/problemset/problem/20/C) |

### Advanced (1600-1900)

| Problem       | Pattern             | Link                                         |
| ------------- | ------------------- | -------------------------------------------- |
| Cycle Finding | Bellman-Ford        | [CSES](https://cses.fi/problemset/task/1197) |
| Investigation | Dijkstra + counting | [CSES](https://cses.fi/problemset/task/1202) |

***

## Key Takeaways

<CardGroup cols={2}>
  <Card title="Dijkstra for Non-Negative" icon="gauge-high">
    O(E log V), most common algorithm in CP.
  </Card>

  <Card title="Bellman-Ford for Negative" icon="gauge">
    O(VE), detects negative cycles.
  </Card>

  <Card title="Floyd for All-Pairs" icon="diagram-project">
    O(V³), when you need all pairs and n ≤ 400.
  </Card>

  <Card title="0-1 BFS for Binary" icon="binary">
    O(V + E), when weights are only 0 and 1.
  </Card>
</CardGroup>

***

## Next Up

<Card title="Chapter 15: Trees" icon="arrow-right" href="/courses/competitive-programming/15-trees">
  Master tree traversals, LCA, and tree DP for hierarchical structures.
</Card>