AdvancedData Structures & Algorithms · Lesson 30 of 40 · Updated ·
Shortest Paths — Dijkstra with a Heap, Bellman-Ford and 0-1 BFS
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 setdist[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.
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))
[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:
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));
}
}
[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.
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))
[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).
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))
[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
intfor distances in Java when the sum of weights can pass about 2.1 × 10⁹; uselong. - 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], updatedist[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).