Shortest Paths: Dijkstra & Bellman-Ford

BFS finds the route with the fewest edges, which is perfect for counting metro stops. But a map app does not care how many roads you take; it cares about the total distance or time. When edges have weights, the path with the fewest edges is often not the shortest one, and you need a different algorithm.

In this lesson you will learn Dijkstra's algorithm, the standard way to find shortest paths when all weights are zero or positive, implement it with a heap, rebuild the actual route, and then see how Bellman-Ford handles negative weights and detects impossible negative cycles.

Why BFS is not enough

Here are three ways from Pune to Nashik in a small example road graph (distances in km are made up). BFS would choose the direct road because it is one edge, but going through two towns is shorter in total.

roads = {
    "Pune": {"Nashik": 250, "Sangamner": 140, "Shirdi": 185},
    "Sangamner": {"Nashik": 70},
    "Shirdi": {"Nashik": 90},
    "Nashik": {},
}
routes = [["Pune", "Nashik"], ["Pune", "Sangamner", "Nashik"], ["Pune", "Shirdi", "Nashik"]]
for r in routes:
    km = sum(roads[a][b] for a, b in zip(r, r[1:]))
    print(f"{' -> '.join(r):28} {len(r) - 1} roads, {km} km")

Pune -> Nashik               1 roads, 250 km
Pune -> Sangamner -> Nashik  2 roads, 210 km
Pune -> Shirdi -> Nashik     2 roads, 275 km

The fewest roads gives 250 km; the shortest distance is 210 km. You need an algorithm that compares total distances.

Dijkstra's algorithm

Dijkstra's algorithm, published by Edsger Dijkstra in 1959, grows a set of vertices whose shortest distance is final, always finalising the closest unfinished vertex next. It keeps a best-known distance for every vertex, starting at 0 for the source and infinity for the rest. Then it repeats:

1. Pick the unfinished vertex with the smallest known distance. Its distance is now final.
2. Relax each of its edges: if going through this vertex gives a neighbour a shorter distance than currently known, update that distance.

Step 1 needs "give me the smallest" again and again, which is exactly what a min-heap does (see Heaps & Priority Queues). Push (distance, vertex) pairs. When a vertex's distance improves, just push a new pair; when an old, larger pair is popped later, skip it. This lazy deletion is simpler than updating items inside the heap.

import heapq
import math

def dijkstra(graph, source):
    dist = {v: math.inf for v in graph}
    parent = {source: None}
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                          # stale entry: skip it
        for v, weight in graph[u].items():
            new = d + weight
            if new < dist[v]:                 # relax the edge u -> v
                dist[v] = new
                parent[v] = u
                heapq.heappush(heap, (new, v))
    return dist, parent

def route(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]

# Example road network (made-up distances in km), roads work both ways
edges = [("Jaipur", "Ajmer", 135), ("Jaipur", "Tonk", 100), ("Tonk", "Bundi", 110),
         ("Ajmer", "Bhilwara", 135), ("Tonk", "Bhilwara", 160), ("Bundi", "Kota", 40),
         ("Bhilwara", "Chittorgarh", 70), ("Kota", "Chittorgarh", 160),
         ("Ajmer", "Udaipur", 320), ("Chittorgarh", "Udaipur", 115)]
graph = {}
for a, b, km in edges:
    graph.setdefault(a, {})[b] = km
    graph.setdefault(b, {})[a] = km

dist, parent = dijkstra(graph, "Jaipur")
for city in ["Kota", "Chittorgarh", "Udaipur"]:
    print(f"{city:12} {dist[city]:>4} km  via {' -> '.join(route(parent, city))}")

Kota          250 km  via Jaipur -> Tonk -> Bundi -> Kota
Chittorgarh   330 km  via Jaipur -> Tonk -> Bhilwara -> Chittorgarh
Udaipur       445 km  via Jaipur -> Tonk -> Bhilwara -> Chittorgarh -> Udaipur

One run from Jaipur gives the shortest distance to every city, and the parent links give each route, the same way as in Breadth-First Search (BFS). The route to Udaipur through Ajmer looks direct, but 135 + 320 = 455 km is longer than the 445 km found.

Each edge can push at most one heap entry, so the heap never holds more than about E entries, and each push or pop costs O(log E). Since E is at most V², log E is at most 2 log V, so Dijkstra with a binary heap runs in O((V + E) log V). If you only need one target, you can stop as soon as that target is popped, because its distance is final at that moment.

Why it works, and when it does not

When Dijkstra pops the closest unfinished vertex u, could a shorter path to u still exist? Any other path must leave the finished set through some vertex that is at least as far as u, and then add more edges. If no edge weight is negative, those extra edges can only add distance, so no other path can beat d. That argument breaks down as soon as an edge can have a negative weight: a path that looks longer at first could become shorter later.

Negative weights appear in real problems. An electric scooter uses battery charge on flat and uphill roads, but regains charge going downhill (regenerative braking). Battery use along a downhill road is negative.

import heapq
import math

def dijkstra(graph, source):
    dist = {v: math.inf for v in graph}
    dist[source] = 0
    heap = [(0, source)]
    done = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in done:
            continue
        done.add(u)                          # Dijkstra treats u as final
        for v, w in graph[u].items():
            if v not in done and d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

# Battery units used on each road; the hill road down to the lake gains charge
battery = {
    "Home": {"Market": 2, "Hilltop": 5},
    "Hilltop": {"Lake": -5},
    "Lake": {"Market": 1},
    "Market": {},
}
print(dijkstra(battery, "Home"))

{'Home': 0, 'Hilltop': 5, 'Lake': 0, 'Market': 2}

Dijkstra says the Market costs 2 units. But the route Home, Hilltop, Lake, Market costs 5 - 5 + 1 = 1 unit. Dijkstra popped the Market at cost 2 and marked it final before it ever explored the downhill road, and it never looks back at a finished vertex. No error is raised; the answer is simply wrong.

Bellman-Ford

The Bellman-Ford algorithm handles negative weights. It is simpler and slower: relax every edge, and repeat that whole pass V - 1 times. A shortest path uses at most V - 1 edges, and pass number k is guaranteed to have found every shortest path that uses k edges, so after V - 1 passes all distances are correct.

It also detects negative cycles: a loop whose total weight is negative. Going round it again and again would make the "shortest" distance fall forever, so no shortest path exists. If a V-th pass can still improve some distance, there must be such a cycle.

import math

def bellman_ford(vertices, edges, source):
    dist = {v: math.inf for v in vertices}
    dist[source] = 0
    for _ in range(len(vertices) - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                            # already settled: stop early
    for u, v, w in edges:                    # one more pass
        if dist[u] + w < dist[v]:
            raise ValueError("negative cycle reachable from the source")
    return dist

vertices = ["Home", "Market", "Hilltop", "Lake"]
edges = [("Home", "Market", 2), ("Home", "Hilltop", 5),
         ("Hilltop", "Lake", -5), ("Lake", "Market", 1)]
print(bellman_ford(vertices, edges, "Home"))

edges.append(("Market", "Hilltop", 1))       # a loop: Hilltop -> Lake -> Market -> Hilltop
try:
    bellman_ford(vertices, edges, "Home")
except ValueError as err:
    print("Error:", err)

{'Home': 0, 'Market': 1, 'Hilltop': 5, 'Lake': 0}
Error: negative cycle reachable from the source

Bellman-Ford finds the true cost of 1 unit to the Market, through Hilltop and Lake, which Dijkstra missed. After the extra road is added, the loop Hilltop, Lake, Market, Hilltop has total weight -5 + 1 + 1 = -3, a scooter that gains charge forever, which is impossible, and Bellman-Ford reports it.

Bellman-Ford takes O(V × E) time, much slower than Dijkstra on big graphs, so use it only when negative weights are possible. Currency exchange is a classic use: with weights set to the negative logarithm of each rate, a negative cycle means an arbitrage opportunity.

Map apps add a further idea on top of Dijkstra, called A* search, which uses an estimate of the remaining distance (such as the straight-line distance to the destination) to explore promising roads first.

Common mistakes

• Using Dijkstra with negative weights. It can return wrong distances without any error. Use Bellman-Ford.
• Using BFS on a weighted graph. BFS minimises the number of edges, not the total weight.
• Not skipping stale heap entries. Without the d > dist[u] check, the algorithm still works but does much more work.
• Marking a vertex final when it is pushed instead of when it is popped. Only the pop guarantees the distance is final.

Key points

• Weighted shortest paths need more than BFS: the fewest edges is not the least total weight.
• Dijkstra repeatedly finalises the closest unfinished vertex and relaxes its edges, using a min-heap.
• With a heap and lazy deletion, Dijkstra runs in O((V + E) log V); store parents to rebuild routes.
• Dijkstra requires non-negative weights.
• Bellman-Ford relaxes every edge V - 1 times in O(V × E), handles negative weights and detects negative cycles.

import heapq
import math

def dijkstra(graph, source):
    dist = {v: math.inf for v in graph}
    parent = {source: None}
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u].items():
            if d + w < dist[v]:
                dist[v] = d + w
                parent[v] = u
                heapq.heappush(heap, (dist[v], v))
    return dist, parent

def route(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]

roads = [("Charbagh", "Hazratganj", 15), ("Charbagh", "Alambagh", 10),
         ("Alambagh", "Gomti Nagar", 30), ("Hazratganj", "Gomti Nagar", 20),
         ("Hazratganj", "Aliganj", 25), ("Gomti Nagar", "Aliganj", 15)]
graph = {}
for a, b, m in roads:
    graph.setdefault(a, {})[b] = m
    graph.setdefault(b, {})[a] = m

for start in ["Charbagh", "Alambagh"]:
    dist, parent = dijkstra(graph, start)
    print(dist["Aliganj"], "min:", " -> ".join(route(parent, "Aliganj")))

40 min: Charbagh -> Hazratganj -> Aliganj
45 min: Alambagh -> Gomti Nagar -> Aliganj