Unit 29: Graph Algorithms
Costs, order and circles.
Unit 29 of 31 in Python for kids. Its 5 lessons are Roads Have Lengths, Dijkstra's Algorithm, Doing Things in Order, Going in Circles and Graph Algorithm Master — below is everything each one explains, and a question or two from it to try.
Every sample on this page was run through real Python before it shipped, and prints exactly what it says it prints.
This unit opens with a fortnight’s trial of everything — no card needed — or with a family plan, bought in the iPhone app. The first two units of every track are free for ever. Try it in the app.
🛣️ Roads Have Lengths
Some edges cost more than others
Until now every connection was the same. A weighted graph gives each edge a cost — minutes, miles, pounds. A dictionary of dictionaries holds it neatly.
Python
roads = {
"a": {"b": 1, "c": 4},
"b": {"c": 1},
"c": {},
}
print(roads["a"]["c"])
print(roads["a"])It prints
4
{'b': 1, 'c': 4}
Fewest roads is not the same as shortest
Here BFS goes straight from a to c in one hop, costing 4. But going a to b to c is two hops and costs only 2. BFS counts steps, not cost — so on a weighted graph it gives the wrong answer.
Python
roads = {
"a": {"b": 1, "c": 4},
"b": {"c": 1},
"c": {},
}
print("direct a->c :", roads["a"]["c"])
print("via b a->b->c :", roads["a"]["b"] + roads["b"]["c"])It prints
direct a->c : 4 via b a->b->c : 2
Adding up a route
The cost of a path is just the sum of the edges along it.
Python
roads = {
"a": {"b": 3},
"b": {"c": 5},
"c": {},
}
path = ["a", "b", "c"]
total = 0
for i in range(len(path) - 1):
total = total + roads[path[i]][path[i + 1]]
print(total)It prints
8
Try it yourself
When is BFS enough to find the cheapest route?
- Always
- Only when every edge costs the same
- Only on small graphs
- Never
Answer it in the app
🧭 Dijkstra's Algorithm
Always deal with the cheapest place next
Dijkstra keeps a best-known cost for every place, and always works on the cheapest one still waiting. Because it never moves to somewhere dearer first, the cost it settles on is final.
Python
best = {"a": 0}
print(best.get("a"))
print(best.get("z"))
print(best.get("z", 999))It prints
0 None 999
A heap hands you the smallest
heapq keeps a pile where the smallest item is always on top. Push (cost, place) pairs and popping gives the cheapest place still to do.
Python
from heapq import heappush, heappop
pile = []
heappush(pile, (5, "c"))
heappush(pile, (1, "a"))
heappush(pile, (3, "b"))
print(heappop(pile))
print(heappop(pile))It prints
(1, 'a') (3, 'b')
The whole algorithm
Take the cheapest waiting place. For each neighbour, if going through here beats the best cost known, write it down and push it. That is all there is to it.
Python
from heapq import heappush, heappop
roads = {
"a": {"b": 1, "c": 4},
"b": {"c": 1, "d": 7},
"c": {"d": 3},
"d": {},
}
def dijkstra(start):
best = {start: 0}
pile = [(0, start)]
while pile:
cost, place = heappop(pile)
if cost > best.get(place, 999999):
continue
for neighbour, price in roads[place].items():
new = cost + price
if new < best.get(neighbour, 999999):
best[neighbour] = new
heappush(pile, (new, neighbour))
return best
for place, cost in sorted(dijkstra("a").items()):
print(place, cost)It prints
a 0 b 1 c 2 d 5
Try it yourself
Why does Dijkstra always take the cheapest place next?
- It is easier to write
- Because no cheaper route can arrive later, so that cost is settled for good
- To save memory
- It does not matter which it takes
What breaks Dijkstra?
- Very large graphs
- An edge with a negative cost
- Loops in the graph
- More than one route
Answer them in the app
📋 Doing Things in Order
Some jobs must come before others
Socks before shoes. A topological sort puts jobs in an order where nothing happens before the thing it depends on. It only works on a graph whose arrows all point one way.
Python
needs = {
"shoes": ["socks"],
"socks": [],
"coat": [],
}
print(needs["shoes"])
print(needs["socks"])It prints
['socks'] []
Count what each job is waiting for
The in-degree of a job is how many things must be done first. Anything with an in-degree of 0 can be done right now.
Python
after = {
"socks": ["shoes"],
"shoes": [],
"shirt": ["coat"],
"coat": [],
}
waiting = {job: 0 for job in after}
for job in after:
for next_job in after[job]:
waiting[next_job] = waiting[next_job] + 1
for job, count in sorted(waiting.items()):
print(job, count)It prints
coat 1 shirt 0 shoes 1 socks 0
Do the free ones, then see what that frees
Take any job waiting on nothing, do it, and take one off the count of everything that was waiting for it. Repeat. This is Kahn's algorithm.
Python
from collections import deque
after = {
"socks": ["shoes"],
"shoes": [],
"shirt": ["coat"],
"coat": [],
}
waiting = {job: 0 for job in after}
for job in after:
for next_job in after[job]:
waiting[next_job] = waiting[next_job] + 1
ready = deque(sorted(j for j in after if waiting[j] == 0))
order = []
while ready:
job = ready.popleft()
order.append(job)
for next_job in sorted(after[job]):
waiting[next_job] = waiting[next_job] - 1
if waiting[next_job] == 0:
ready.append(next_job)
print(order)It prints
['shirt', 'socks', 'coat', 'shoes']
Try it yourself
Can a topological sort have more than one right answer?
- No, there is always exactly one
- Yes — jobs that do not depend on each other can go in either order
- Only for small graphs
- Only if there is a cycle
Answer it in the app
🔄 Going in Circles
When the jobs wait for each other
If a needs b, and b needs a, no order can ever work. That is a cycle — and Kahn's algorithm spots it for free: if some jobs never became ready, they are stuck in a circle.
Python
from collections import deque
after = {"a": ["b"], "b": ["a"]}
waiting = {job: 0 for job in after}
for job in after:
for nxt in after[job]:
waiting[nxt] = waiting[nxt] + 1
ready = deque(j for j in after if waiting[j] == 0)
done = 0
while ready:
job = ready.popleft()
done = done + 1
for nxt in after[job]:
waiting[nxt] = waiting[nxt] - 1
if waiting[nxt] == 0:
ready.append(nxt)
print(done, len(after))
print("cycle!" if done < len(after) else "fine")It prints
0 2 cycle!
Finding one with DFS instead
Walking the graph, keep track of the nodes on the path you are *currently* down. Meeting one of those again means you have gone in a circle.
Python
graph = {"a": ["b"], "b": ["c"], "c": ["a"]}
visiting = set()
done = set()
def has_cycle(node):
if node in visiting:
return True
if node in done:
return False
visiting.add(node)
for neighbour in graph[node]:
if has_cycle(neighbour):
return True
visiting.discard(node)
done.add(node)
return False
print(has_cycle("a"))It prints
True
Two paths to the same place is not a cycle
Here both b and c lead to d. Nothing loops back, so there is no cycle — and this is exactly what the "finished" set is protecting.
Python
graph = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}
visiting = set()
done = set()
def has_cycle(node):
if node in visiting:
return True
if node in done:
return False
visiting.add(node)
for neighbour in graph[node]:
if has_cycle(neighbour):
return True
visiting.discard(node)
done.add(node)
return False
print(has_cycle("a"))It prints
False
Try it yourself
Why is "already finished" different from "currently on the path"?
- They are the same thing
- Reaching a finished node again is fine — only meeting one still on the current path means a circle
- Finished nodes are always cycles
- To save memory
Answer it in the app
🏆 Graph Algorithm Master
Try it yourself
What does this print?
Python
from heapq import heappush, heappop
pile = []
heappush(pile, (4, "d"))
heappush(pile, (2, "b"))
heappush(pile, (2, "a"))
print(heappop(pile))Answer it in the app