# Shortest Paths — Part 1: The Pattern

"Shortest" depends on the edges. With **no weights** (every step costs 1), plain **BFS** is optimal. With **non-negative weights**, use **Dijkstra's algorithm**: always expand the closest unfinished node, using a min-heap. With **negative weights** or a **limit on the number of edges**, use **Bellman-Ford** (relax every edge repeatedly). For **all pairs** on small graphs, **Floyd–Warshall**. Picking the right one, and explaining why, is most of the interview.

![Dijkstra settles nodes in order of distance, relaxing their outgoing edges](diagrams/01-dijkstra.svg)

## 1. Choosing an Algorithm

| Graph | Algorithm | Complexity |
|---|---|---|
| unweighted (or all weights equal) | BFS | O(V + E) |
| weights 0 or 1 | **0-1 BFS** with a deque (0-edges to the front) | O(V + E) |
| non-negative weights | **Dijkstra** + min-heap | O((V + E) log V) |
| negative weights, or "at most k edges/stops" | **Bellman-Ford** (k + 1 rounds) | O(V · E) or O(k · E) |
| all pairs, V ≤ ~400 | **Floyd–Warshall** | O(V³) |
| "minimize the maximum edge on the path" | Dijkstra with `max` instead of `+`, or binary search + BFS, or union-find | O(E log V) |

## 2. Dijkstra Template

```typescript
class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

function dijkstra(n: number, edges: number[][], src: number): number[] {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) adj[u].push([v, w]);
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  const heap = new MinHeap<[number, number]>((a, b) => a[0] < b[0]);
  heap.push([0, src]);
  while (heap.size) {
    const [d, u] = heap.pop()!;
    if (d > dist[u]) continue;
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) { dist[v] = d + w; heap.push([dist[v], v]); }
    }
  }
  return dist.map((x) => (x === Infinity ? -1 : x));
}
```

```python
import heapq

def dijkstra(n, edges, src):                    # edges: (u, v, w) with w >= 0, directed
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    dist = [float("inf")] * n
    dist[src] = 0
    heap = [(0, src)]                           # (distance, node)
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                            # stale entry: a shorter path was found already
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:                    # relax
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return [x if x != float("inf") else -1 for x in dist]
```

**Relaxation:** if going through u gives v a shorter distance, update `dist[v]` and push the new pair. The `if d > dist[u]: continue` line skips **stale heap entries** (lazy deletion), which is simpler than a decrease-key operation and is what interviewers expect.

## 3. Why Dijkstra Fails With Negative Edges

Dijkstra assumes that once a node is popped with distance d, nothing can later offer a shorter path, because every remaining path is at least d and adding non-negative edges can't shrink it. A negative edge breaks that guarantee: a longer route through a negative edge can end up shorter than a distance already finalized. Bellman-Ford doesn't finalize anything; it simply relaxes all edges V − 1 times (one more round that still improves something reveals a **negative cycle**).

## 4. Bellman-Ford With k Stops

To find the cheapest route using at most k + 1 edges, run k + 1 rounds of relaxing every edge, and in each round read distances from a **copy of the previous round**. That copy ensures each round extends paths by exactly one edge. This is Cheapest Flights Within K Stops.

## Under the Hood: Real Routing

Maps use Dijkstra variants with heuristics: **A\*** adds an admissible estimate of the remaining distance (straight-line distance) so the search heads toward the goal; production routers (OSRM, Google Maps) precompute **contraction hierarchies** so continent-scale queries take milliseconds. Network routing protocols are distributed versions: OSPF runs Dijkstra on each router's view of the topology, while RIP is distance-vector, essentially Bellman-Ford.

## Common Pitfalls

1. **Using Dijkstra with negative edges.**
2. **Not skipping stale heap entries**, which processes nodes many times (still correct but slow) or, with a naive "visited" check placed wrong, gives wrong answers.
3. **Bellman-Ford without copying the previous round** when the number of edges is limited.
4. **Overflow:** `INF + w` in C#/Java `int`; use `long` or check before adding.
5. **Using DFS for shortest paths:** DFS finds *a* path, not the shortest.

## Quick Reference

```text
unweighted → BFS · 0/1 weights → deque · w ≥ 0 → Dijkstra · negatives / ≤k edges → Bellman-Ford
Dijkstra: heap (0, src); pop (d,u); skip if d > dist[u]; relax v: if d+w < dist[v] → update, push
Bellman-Ford k stops: repeat k+1: tmp = dist[:]; for u,v,w: tmp[v] = min(tmp[v], dist[u]+w); dist = tmp
```