Unit 9: Shortest Roads

Roads have lengths now, and BFS is finished

Fewest roads is not cheapest journey. Two short hops can easily beat one long one, and BFS counts hops.

Every algorithm in this unit is built from one move, called relaxing an edge: if going to a and then along the road to b beats what you had written down for b, write down the better number.

Relax every road, over and over

Write 0 for the start and "unknown" for everything else, then relax every edge, n - 1 times over. That is Bellman–Ford.

The edges here are deliberately listed in an unhelpful order so you can watch the answers crawl outwards one round at a time.

Python

n = 5
edges = [(3, 4, 2), (2, 3, 9), (1, 3, 6), (2, 4, 7), (2, 1, 1), (0, 2, 3), (0, 1, 5)]
big = 99

dist = [big] * n
dist[0] = 0

for round in range(n - 1):
    for a, b, w in edges:
        if dist[a] + w < dist[b]:
            dist[b] = dist[a] + w
    print(dist)

It prints

[0, 5, 3, 99, 99]
[0, 4, 3, 11, 10]
[0, 4, 3, 10, 10]
[0, 4, 3, 10, 10]

Why n - 1 rounds is always enough

A shortest route can visit each node at most once, so it uses at most n - 1 roads. After one round every one-road route is known, after two rounds every two-road route, and so on.

Cost: rounds times edges, so O(n * m). Slow — but it is the only one here that survives a negative road.

And an extra round is a lie detector

If anything still improves on round n, some loop makes the journey cheaper every time round it. That is a negative cycle, and "the shortest path" then has no answer at all.

The distances printed below are not wrong so much as meaningless — go round the loop again and they drop again. Contests ask for exactly this check, so run one more round and report it.

Python

n = 3
edges = [(0, 1, 1), (1, 2, -1), (2, 1, -1)]
big = 99

dist = [big] * n
dist[0] = 0
for round in range(n - 1):
    for a, b, w in edges:
        if dist[a] + w < dist[b]:
            dist[b] = dist[a] + w

changed = False
for a, b, w in edges:
    if dist[a] + w < dist[b]:
        changed = True

print(dist, changed)

It prints

[0, -3, -2] True

Relax in the right order and once is enough

Bellman–Ford relaxes everything again and again because it does not know which nodes are finished. Dijkstra always works on the nearest unfinished node — and once you are working on it, nothing can ever make it cheaper.

So every node is dealt with once, and the cost drops from n * m to about m log n.

The heap picks the nearest one for you

heapq keeps the smallest item at the front. Push (distance, node), always pop the smallest, and skip anything you have already beaten.

Watch the order the nodes come out in: 0, 2, 1, 3, 4 — nearest first, never in the order they were found.

Python

import heapq

n = 5
roads = [(0, 1, 5), (0, 2, 3), (2, 1, 1), (1, 3, 6), (2, 3, 9), (2, 4, 7), (3, 4, 2)]
adj = [[] for i in range(n)]
for a, b, w in roads:
    adj[a].append((b, w))

big = 10 ** 9
dist = [big] * n
dist[0] = 0
heap = [(0, 0)]
order = []

while heap:
    d, node = heapq.heappop(heap)
    if d > dist[node]:
        continue
    order.append(node)
    for nxt, w in adj[node]:
        if d + w < dist[nxt]:
            dist[nxt] = d + w
            heapq.heappush(heap, (dist[nxt], nxt))

print(dist)
print(order)

It prints

[0, 4, 3, 10, 10]
[0, 2, 1, 3, 4]

The skip line is not optional

A node can be pushed several times, once for each better route found. if d > dist[node]: continue throws away the stale copies.

Without it the algorithm still gets the right answer and gets slower and slower on big graphs, which is the worst kind of bug: invisible on your test, fatal on theirs.

A negative road breaks it, and here is the exact moment

Dijkstra closes node 1 at distance 2, because 2 is the smallest thing on the heap — and immediately sends 1 onward to node 3, arriving at 4.

Then the road from 2 to 1 turns out to cost -4, so node 1 was really only 1 away. Too late: it is closed, and node 3 keeps the stale 4. Bellman–Ford never closes anything, and gets 3.

Python

import heapq

roads = [(0, 1, 2), (1, 3, 2), (0, 2, 5), (2, 1, -4)]
n = 4
adj = [[] for i in range(n)]
for a, b, w in roads:
    adj[a].append((b, w))

big = 99
dist = [big] * n
dist[0] = 0
heap = [(0, 0)]
done = [False] * n
while heap:
    d, node = heapq.heappop(heap)
    if done[node]:
        continue
    done[node] = True
    for nxt, w in adj[node]:
        if d + w < dist[nxt]:
            dist[nxt] = d + w
            heapq.heappush(heap, (dist[nxt], nxt))

slow = [big] * n
slow[0] = 0
for round in range(n - 1):
    for a, b, w in roads:
        if slow[a] + w < slow[b]:
            slow[b] = slow[a] + w

print(dist)
print(slow)

It prints

[0, 1, 5, 4]
[0, 1, 5, 3]

Sometimes the question is about every pair

"How far is it from anywhere to anywhere?" Running Dijkstra from every node works. For small graphs there is something shorter to write and much easier to get right.

Floyd–Warshall: three nested loops over a table of distances, and that is the entire algorithm.

Let each node take a turn as a stopping point

The outer loop is not a node you are going to — it is a node you are allowed to stop at. After the round for k, the table holds the best journey using only stops from the ones tried so far.

The order of the loops matters completely: k on the outside, always.

Python

big = 99
n = 4
d = [
    [0, 5, big, 10],
    [big, 0, 3, big],
    [big, big, 0, 1],
    [big, big, big, 0],
]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][k] + d[k][j] < d[i][j]:
                d[i][j] = d[i][k] + d[k][j]

for row in d:
    print(row)

It prints

[0, 5, 8, 9]
[99, 0, 3, 4]
[99, 99, 0, 1]
[99, 99, 99, 0]

Nine beats ten

There is a direct road from 0 to 3 costing 10. Going 0 to 1 to 2 to 3 costs 5 + 3 + 1 = 9, and the table found it.

Cost: n * n * n. At 500 nodes that is 125 million — just about affordable, and about the limit. Past that, run Dijkstra from each node instead.

Four algorithms, one question each

Every edge costs the same → BFS, O(n + m).

One start, no negative roads → Dijkstra, about m log n.

One start, negative roads allowed → Bellman–Ford, n * m, and it detects a negative cycle.

Every pair, and n is small → Floyd–Warshall, n * n * n.

The numbers that make the choice for you

With 100000 nodes and 200000 roads, Dijkstra is about three and a half million steps and Bellman–Ford is twenty thousand million. There is nothing to think about.

With 300 nodes, Floyd–Warshall is 27 million and takes four lines. Also nothing to think about.

Python

import math

n = 100000
m = 200000
print("dijkstra", m * math.floor(math.log2(n)))
print("bellman", n * m)
print("floyd 300", 300 ** 3)

It prints

dijkstra 3200000
bellman 20000000000
floyd 300 27000000

The negative cycle question is a real one

A currency exchange where a loop of trades leaves you richer, a game where a loop scores points for ever — problems are written around exactly this, and the answer they want is "there is no cheapest journey".

One extra Bellman–Ford round finds it. Nothing else in the unit can.