Dijkstra's shortest path algorithm in Python

Problem

Fewest streets is not fastest

A courier leaves the depot for a client. The app has to give the fastest route. Every street has a time in minutes: the boulevard is wide but jammed, and the small side streets are quick.

The city is a graph, and the streets are its edges in both directions (see representing a graph):

def add_street(city, a, b, minutes):
    city.setdefault(a, []).append((b, minutes))
    city.setdefault(b, []).append((a, minutes))

city = {}
add_street(city, "Depot", "Bridge", 2)
add_street(city, "Depot", "Square", 5)
add_street(city, "Depot", "Market", 15)
add_street(city, "Bridge", "Square", 1)
add_street(city, "Bridge", "Station", 8)
add_street(city, "Square", "Station", 3)
add_street(city, "Square", "Market", 9)
add_street(city, "Station", "Client", 3)
add_street(city, "Market", "Client", 2)

The first idea is BFS from the previous lesson: it finds the shortest path. But BFS counts streets, not minutes:

def fewest_streets(city, start):
    prev = {}
    seen = {start}
    queue = deque([start])
    while queue:
        place = queue.popleft()
        for to, _ in city[place]:
            if to not in seen:
                seen.add(to)
                prev[to] = place
                queue.append(to)
    return prev

city = {}
add_street(city, "Depot", "Bridge", 2)
add_street(city, "Depot", "Square", 5)
add_street(city, "Depot", "Market", 15)
add_street(city, "Bridge", "Square", 1)
add_street(city, "Bridge", "Station", 8)
add_street(city, "Square", "Station", 3)
add_street(city, "Square", "Market", 9)
add_street(city, "Station", "Client", 3)
add_street(city, "Market", "Client", 2)
r = route(fewest_streets(city, "Depot"), "Client")
print(f"Fewest streets: {' → '.join(r)} ({len(r) - 1} streets, {minutes(city, r)} min)")

Fewest streets: Depot → Market → Client (2 streets, 17 min)

Two streets, but 17 minutes: 15 along the boulevard to the market and 2 to the client. Through the bridge, the square and the station it is four streets and only 9 minutes. BFS does not even look at the minutes.

The idea

The nearest place first

BFS goes by number of streets: first everything one street away, then two. Here you have to go by minutes: first the place you reach fastest, then the next one.

That is Dijkstra’s algorithm (Edsger Dijkstra, 1956). For every place it keeps the best time so far, dist, plus a queue of “minutes, place” entries.

At the start dist is 0 for the depot, and every other place is unreached (∞).
Take the entry with the fewest minutes from the queue. That is a priority queue: it removes the smallest in O(log n).
For every street from that place, try: does it reach the neighbour faster than before? If so, write down the new time, remember where you came from (prev) and put a new entry in the queue. This trying is called relaxation.
Repeat until the queue is empty.

Why does the place that leaves the queue already have its final time? All other entries have at least as many minutes, and every street adds minutes. No path through them can arrive earlier.

See it

Dijkstra from the inside

def dijkstra(city, start):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, place = heapq.heappop(queue)
        if minutes > dist[place]:
            continue  # stale
        for to, length in city[place]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = place
                heapq.heappush(queue, (t, to))
    return dist, prev

heapq compares tuples from left to right: (minutes, place) comes out by minutes. A place missing from dist is not reached yet: that is ∞.

prev keeps the route backwards: for every place, where the fastest path came from. You start at the client, follow prev to the depot and turn it round:

def route(prev, end):
    places = []
    at = end
    while at is not None:
        places.append(at)
        at = prev.get(at)
    return places[::-1]

dist, prev = dijkstra(city, "Depot")
r = route(prev, "Client")
print(f"Fastest: {' → '.join(r)} ({len(r) - 1} streets, {minutes(city, r)} min)")

Fastest: Depot → Bridge → Square → Station → Client (4 streets, 9 min)

def dijkstra(city, start):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, place = heapq.heappop(queue)
        if minutes > dist[place]:
            continue  # stale
        for to, length in city[place]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = place
                heapq.heappush(queue, (t, to))
    return dist, prev

Step by step, in words

The courier starts at the Depot: 0 minutes. Every other place is ∞, nothing has reached it yet. The queue holds a single entry: 0 Depot.
Take the smallest entry, 0 Depot. Each street from it gives a time: Bridge 2, Square 5, Market 15. All are better than ∞: they are written down and go into the queue.
Next is 2 Bridge. Through it the Square is 2 + 1 = 3, better than 5: the time and prev change, and 3 Square goes in. The old 5 Square stays in the queue, it is now stale. The Station gets 10.
3 Square: final, nothing in the queue can make it faster. Through it the Station drops from 10 to 6 and the Market from 15 to 12.
On top is 5 Square, but the Square already has 3. The entry is stale: skip it. That is the lazy deletion: instead of searching the queue for the old entry, you throw it away when it comes out.
6 Station: final. The Client gets 6 + 3 = 9. The way back, Bridge with 14 and Square with 9, is no better.
9 Client: final, 9 minutes. Through the Client the Market drops from 12 to 11. The frontier grows by time, not by number of streets.
The rest: 10 Station is stale, 11 Market is final and improves nothing, 12 and 15 Market are stale. The queue is empty.
prev gives the route backwards: Client ← Station ← Square ← Bridge ← Depot. Turned round: Depot → Bridge → Square → Station → Client, 9 minutes, four streets. The two-street route through the Market takes 17.

Places become final in order of their time: Depot 0, Bridge 2, Square 3, Station 6, Client 9, Market 11. The market, one street from the depot, is last.

Try it

Predict the output

How many minutes to the market does Dijkstra give?

city = {}
add_street(city, "Depot", "Bridge", 2)
add_street(city, "Depot", "Square", 5)
add_street(city, "Depot", "Market", 15)
add_street(city, "Bridge", "Square", 1)
add_street(city, "Bridge", "Station", 8)
add_street(city, "Square", "Station", 3)
add_street(city, "Square", "Market", 9)
add_street(city, "Station", "Client", 3)
add_street(city, "Market", "Client", 2)
dist, prev = dijkstra(city, "Depot")
print(dist["Market"])

Answer

The idea

Stale entries

When the square gets 3 minutes instead of 5, the entry “5 Square” is already in the queue. Why not change it in place?

Built-in queues cannot: Python’s heapq is just functions over a list, with no “change priority”. So the better time goes in as a new entry. The old one stays, and when it comes out, the check throws it away: its time is greater than the one in dist. This is lazy deletion.

The queue can hold more entries than places, at most one per street. The price is a little memory and a few empty takes.

minutes, place = heapq.heappop(queue)
if :
    continue  # stale

Try it

Find the bug

A colleague decided that the first time found is also the best, as in BFS:

def dijkstra(city, start):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, place = heapq.heappop(queue)
        if minutes > dist[place]:
            continue  # stale
        for to, length in city[place]:
            t = minutes + length
            if to not in dist:
                dist[to] = t
                prev[to] = place
                heapq.heappush(queue, (t, to))
    return dist, prev

dist, prev = dijkstra(city, "Depot")
r = route(prev, "Client")
print(f"Fastest: {' → '.join(r)} ({len(r) - 1} streets, {minutes(city, r)} min)")

Fastest: Depot → Bridge → Station → Client (3 streets, 13 min)

13 minutes instead of 9. Which line has the bug?

Pick the line with the bug.

The idea

What it costs

Every street is tried twice (once from each end) and can add an entry. Every entry goes in and comes out once, at O(log V). In total O((V + E) log V) for V places and E streets.

Without the queue, the nearest place is found with a loop over all places that are not final yet. That is how the algorithm was originally written:

def dijkstra_scan(city, start):
    dist = {place: math.inf for place in city}
    dist[start] = 0
    done = set()
    while len(done) < len(city):
        best = None
        for place in city:
            if place not in done and (best is None or dist[place] < dist[best]):
                best = place
        if dist[best] == math.inf:
            break
        done.add(best)
        for to, length in city[best]:
            t = dist[best] + length
            if t < dist[to]:
                dist[to] = t
    return dist

city = {}
add_street(city, "Depot", "Bridge", 2)
add_street(city, "Depot", "Square", 5)
add_street(city, "Depot", "Market", 15)
add_street(city, "Bridge", "Square", 1)
add_street(city, "Bridge", "Station", 8)
add_street(city, "Square", "Station", 3)
add_street(city, "Square", "Market", 9)
add_street(city, "Station", "Client", 3)
add_street(city, "Market", "Client", 2)
dist = dijkstra_scan(city, "Depot")
print(", ".join(f"{p} {dist[p]}" for p in ["Depot", "Bridge", "Square", "Station", "Market", "Client"]))

Depot 0, Bridge 2, Square 3, Station 6, Market 11, Client 9

The answer is the same. But the loop is V steps, and it runs V times: O(V²).

Run both versions on a district where the crossings form a grid, each one linked to its right and lower neighbour. Every street takes 1 to 9 minutes. Every comparison of two times is counted: when looking for the nearest place, inside the queue and when trying a street.

No queue: a loop for the nearest O(n²)
With a priority queue O(n log n)

Algorithm	n = 100	n = 1,000	n = 10,000	n = 100,000
No queue: a loop for the nearest	5,410	504,372	≈ 50,437,200	≈ 5,043,720,000
With a priority queue	1,269	17,121	213,675	2,554,618

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

def dijkstra(city, start):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, place = heapq.heappop(queue)
        if minutes > dist[place]:
            continue  # stale
        for to, length in city[place]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = place
                heapq.heappush(queue, (t, to))
    return dist, prev

At 1000 crossings the version without a queue makes 504 372 comparisons, the one with a queue 17 121. At 100 000 crossings, the size of a big city, the queue makes 2 554 618. Without it there would be about 5 billion: Bench does not run them but estimates them from the curve.

More precisely, if you are curious

When is O(V²) better? When the graph is dense: every place is linked to almost every other, and E is about V². Then the queue does O(V² log V) and the loop O(V²). In a road network every crossing has 3–4 streets, the graph is sparse and the queue wins.

Negative weights break Dijkstra. If a street costs −5 (say, a delivery bonus on the way), a place that is already final can become nearer through it later, and the algorithm no longer looks at it. Such graphs need Bellman-Ford: it tries every street V − 1 times, O(V · E), and reports a cycle that lowers the time forever.

In Python ∞ is math.inf: math.inf + 5 is still math.inf, and integers do not overflow. In Java and C# ∞ is usually the largest int, and adding minutes to it gives a negative number.

The navigation on your phone does not run Dijkstra over a whole continent. It uses A*: Dijkstra that adds to the minutes in the queue an estimate of how much is left in a straight line, so it heads for the goal instead of spreading in every direction. OSPF, the protocol routers in one network use to find the path for packets, runs real Dijkstra.

Exercise

A closed street

Solve it in your editor.

Roadworks. The street between the bridge and the square is closed. Remove it from the city (in both directions) and print the fastest route and minutes to the station, the client and the market:

Station: Depot → Square → Station (8 min)
Client: Depot → Square → Station → Client (11 min)
Market: Depot → Square → Station → Client → Market (13 min)

The market is still fastest through the client: 13 minutes against 14 through the square and 15 along the boulevard.

More tasks

Stop in time. If you only care about the client, stop as soon as it leaves the queue. How many entries are left untaken?
Count the takes. Count how many entries left the queue and how many of them were stale.
Two couriers. Two depots, one client: which courier gets there first? Hint: put both depots in the queue with 0 minutes.

Test

Check yourself

1. Why does BFS not find the fastest route when streets have minutes?BFS does not reach every placeBFS only works on treesBFS counts streets: it finds the path with the fewest streets, and that can be slower

2. A place leaves the queue with the fewest minutes of all entries. Why is its time final?Every other path goes through a place with at least as many minutes, and streets are not negativeBecause the queue is ordered by number of streetsBecause nothing points to it

3. The queue holds 5 Square, and the Square already has 3 minutes. What does the algorithm do when 5 Square comes out?Changes the Square’s time to 5Stops: a cycle was foundSkips it: the entry is stale

4. How much does Dijkstra with a binary heap cost for V places and E streets?O(V + E)O((V + E) log V)O(V²)

Dijkstra

Cookies