# Shortest Paths — Dijkstra with a Heap, Bellman-Ford and 0-1 BFS

Source: https://skills101.in/learn/dsa/dsa-shortest-paths-dijkstra-bellman-ford — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-21.

Plain BFS finds the path with the **fewest edges**. But in a road map the edges have **weights** — distances, fares or travel times — and the path with fewest roads is not always the cheapest. This lesson covers the three shortest-path methods you need for placements: **Dijkstra**, **Bellman-Ford** and **0-1 BFS**.

All three solve the **single-source** problem: the shortest distance from one start node to every other node.

## 1. The key step: relaxing an edge

Every shortest-path algorithm keeps `dist[v]`, the best distance to `v` found so far (start: 0 for the source, ∞ for the rest). **Relaxing** an edge u → v with weight w means:

> if `dist[u] + w < dist[v]`, then set `dist[v] = dist[u] + w` (going through u is better).

The algorithms differ only in **which** edges they relax and in **what order**.

## 2. Dijkstra's algorithm

**Idea:** always settle the unvisited node with the **smallest** known distance next. With **non-negative** weights, no later path can make that node cheaper — any other path would have to pass through nodes that are already at least as far away.

A min-heap gives "the smallest distance" quickly. Python's `heapq` cannot lower a value already in the heap, so we simply push a new `(distance, node)` pair and **skip stale entries** when they are popped.

![A weighted graph with nodes A to E; shortest distances from A are A 0, C 1, B 3, D 4, E 7; the direct edge A-B of weight 4 is not used because A-C-B costs 3](https://skills101.in/learn-img/dsa/dijkstra-graph.svg)

![Dijkstra trace table: pop A (0) improves B to 4 and C to 1; pop C (1) improves B to 3 and D to 6; pop B (3) improves D to 4; a stale B entry with 4 is skipped; pop D (4) improves E to 7; a stale D entry with 6 is skipped; pop E (7)](https://skills101.in/learn-img/dsa/dijkstra-steps.svg)

```python
import heapq

def dijkstra(n, edges, src):
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))          # undirected roads
    dist = [float('inf')] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                   # stale entry: a shorter one was found
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist

# A=0, B=1, C=2, D=3, E=4
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3)]
print(dijkstra(5, edges, 0))
```

```text
[0, 3, 1, 4, 7]
```

**Cost:** O((V + E) log V) with a binary heap. To print the actual route, also store `parent[v] = u` whenever you relax, then walk back from the target.

The Java version uses a `PriorityQueue` of `int[]{distance, node}` pairs:

```java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 1}, {2, 3, 5}, {3, 4, 3}};
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[1], e[2]});
            adj.get(e[1]).add(new int[]{e[0], e[2]});
        }
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[0] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.add(new long[]{0, 0});
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            long d = top[0];
            int u = (int) top[1];
            if (d > dist[u]) continue;
            for (int[] e : adj.get(u)) {
                if (d + e[1] < dist[e[0]]) {
                    dist[e[0]] = d + e[1];
                    pq.add(new long[]{dist[e[0]], e[0]});
                }
            }
        }
        System.out.println(Arrays.toString(dist));
    }
}
```

```text
[0, 3, 1, 4, 7]
```

## 3. Why Dijkstra fails with negative edges

Suppose A → B costs 2, A → C costs 3 and C → B costs −2. Dijkstra settles B with distance 2 first (it is the smallest), and never revisits it. But A → C → B costs 3 + (−2) = 1. The "smallest so far is final" idea breaks as soon as an edge can **reduce** a total. For negative weights, use Bellman-Ford.

## 4. Bellman-Ford

Relax **every** edge, and repeat that **V − 1** times. A shortest path without cycles has at most V − 1 edges, and each round fixes at least one more edge of it.

Then do **one more** round: if any distance still improves, the graph has a **negative cycle** reachable from the source — going round it again and again lowers the cost forever, so "shortest" has no meaning.

```python
def bellman_ford(n, edges, src):
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:            # directed edges
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                         # early stop: nothing improved
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None                   # negative cycle
    return dist

print(bellman_ford(3, [(0, 1, 2), (0, 2, 3), (2, 1, -2)], 0))
print(bellman_ford(3, [(0, 1, 1), (1, 2, -1), (2, 1, -1)], 0))
```

```text
[0, 1, 3]
None
```

**Cost:** O(V · E) — slower than Dijkstra, but it handles negative edges. A common variant, "cheapest flights within K stops", runs only K + 1 rounds (copying `dist` each round so a round uses only the previous round's values).

## 5. 0-1 BFS

When every edge weight is **0 or 1** (for example, "free move" vs "costs one wall break"), you do not need a heap. Use a **deque**: after relaxing an edge of weight 0, push the node to the **front**; for weight 1, push it to the **back**. The deque then always holds nodes in order of distance, like a heap would, and the cost is **O(V + E)**.

```python
from collections import deque

def zero_one_bfs(n, edges, src):
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    dist = [float('inf')] * n
    dist[src] = 0
    dq = deque([src])
    while dq:
        u = dq.popleft()
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

print(zero_one_bfs(4, [(0, 1, 1), (0, 2, 0), (2, 1, 0), (1, 3, 1), (2, 3, 1)], 0))
```

```text
[0, 0, 0, 1]
```

## 6. Which one to use

| Graph | Use | Time |
|---|---|---|
| no weights (or all equal) | BFS | O(V + E) |
| weights only 0 or 1 | 0-1 BFS | O(V + E) |
| non-negative weights | Dijkstra with a heap | O((V + E) log V) |
| some negative weights, or "at most K edges" | Bellman-Ford | O(V · E) |
| all pairs, small V (up to a few hundred) | Floyd-Warshall | O(V³) |

## Common mistakes

- Running Dijkstra on a graph with negative edges. It can return wrong answers without any error.
- Forgetting the stale-entry check `if d > dist[u]: continue`. The answer stays correct, but the work can grow a lot.
- Using `int` for distances in Java when the sum of weights can pass about 2.1 × 10⁹; use `long`.
- Running Bellman-Ford only V − 2 rounds, or forgetting the extra round that detects a negative cycle.
- Treating an undirected road as one directed edge; add both directions.

## Quick recap

- Relax: if `dist[u] + w < dist[v]`, update `dist[v]`.
- Dijkstra: pop the smallest distance from a min-heap, relax its edges, skip stale entries; non-negative weights only.
- Bellman-Ford: relax all edges V − 1 times; one more improving round means a negative cycle.
- 0-1 BFS: deque, weight-0 edges to the front, weight-1 edges to the back; O(V + E).


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-shortest-paths-dijkstra-bellman-ford