Lesson 11 of 16

Compute Shortest Distances with Dijkstra

When edge travel times differ, BFS’s fewest-edge path need not be fastest. Dijkstra processes the vertex with the smallest currently known distance first. All weights must be nonnegative.

Reinsert only when a distance improves

Vertex names are strings, and every vertex is a dictionary key. These edges are directed: A-B costs 3, B-C costs 2, and A-C costs 8.

import heapq

def shortest_distances(graph, start):
    if any(w < 0 for edges in graph.values() for w in edges.values()):
        raise ValueError("Nonnegative weights required")
    distance = {node: float("inf") for node in graph}
    distance[start] = 0
    pending = [(0, start)]
    while pending:
        cost, node = heapq.heappop(pending)
        if cost != distance[node]:
            continue
        for neighbor, weight in graph[node].items():
            candidate = cost + weight
            if candidate < distance[neighbor]:
                distance[neighbor] = candidate
                heapq.heappush(pending, (candidate, neighbor))
    return distance

graph = {"A": {"B": 3, "C": 8}, "B": {"C": 2}, "C": {}}
print(shortest_distances(graph, "A")["C"])

The result is 5. Going through B costs less than the direct edge costing 8. A vertex may enter the heap more than once. When an outdated entry is removed, comparing it with the current distance lets us skip it.

Why settle the closest vertex first?

With nonnegative weights, a route through a currently more distant vertex cannot improve the smallest current distance. Negative edges break that reasoning. Problems with negative weights need another method, such as Bellman-Ford.

For a simple graph using a binary heap, time is O((V+E) log V). Unreachable vertices remain at infinity. To recover routes as well as distances, save a predecessor when improving each distance and trace backward.

Check your understanding

Suppose A-B costs 3, A-C costs 5, and C-B costs -4. What is the shortest distance to B? Is Dijkstra’s basic settling rule still justified?