Dijkstra's Shortest Path

When roads have lengths

BFS finds the path with the fewest edges. But with road lengths, two short roads can beat one long road. Dijkstra's algorithm finds the shortest total distance from a start to every other place, as long as no road has a negative length.

The idea

• Every place starts at distance ∞, except the start at 0.
• Repeatedly pick the closest place not yet finished (a min-heap does this fast).
• From it, check each road: if going through this place gives a shorter distance to a neighbour, update it.

Think of it like this: Spilling water at the start: it spreads along the roads at a steady speed, and reaches each place for the first time along the shortest route. Dijkstra always finishes the place the water would reach next.

import heapq

graph = {
    "A": [("B", 4), ("C", 1)],
    "B": [("D", 1)],
    "C": [("B", 2), ("D", 5)],
    "D": [],
}

def dijkstra(start):
    dist = {node: float("inf") for node in graph}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue                       # an old, longer entry - skip it
        for nxt, length in graph[node]:
            if d + length < dist[nxt]:
                dist[nxt] = d + length
                heapq.heappush(heap, (dist[nxt], nxt))
    return dist

print(dijkstra("A"))

Output

{'A': 0, 'B': 3, 'C': 1, 'D': 4}

A → C → B → D is 1 + 2 + 1 = 4, shorter than A → B → D (4 + 1 = 5). Time: O((V + E) log V).

Common mistake: Dijkstra gives wrong answers if any edge has a negative weight. (The Bellman-Ford algorithm handles those.)