City navigation with BFS and Dijkstra in Python

Problem

The courier asks for a route

The courier company from the "Graphs" module has a depot in the city. The map is a text file with one street per line: from where, to where and how many minutes it takes to drive. - is a two-way street, -> is one-way:

Depot - Station 4
Depot - Market 3
Station - Square 3
Market - Square 2
Market -> Park 4
Square - Cinema 5
Cinema - Hospital 3
Park - Stadium 2
Stadium - Hospital 2
Depot - Stadium 16

The dispatcher needs a route from the Depot to the Hospital. The courier on a bicycle asks for the route with the fewest crossroads, because they stop at every one. The courier in the van asks for the fastest. The answers are not the same.

This project is the program that reads the map and answers both questions. You build it in steps, each with output to compare yours against.

The idea

The plan

The map as a graph. Crossroads are vertices, streets are weighted edges: the minutes. As in "Graph: adjacency list and matrix", you keep an adjacency list: a map from a crossroad to a list of streets.
Fewest streets. BFS from the Depot in layers: first the crossroads one street away, then two.
The minutes of a route. The sum of the minutes of its streets, to compare the two answers.
Fastest. Dijkstra with a priority queue: it always takes out the crossroad with the fewest minutes so far.
The way back. The same program from the Hospital to the Depot. The one-way street makes the way back different.

The program reads the map from standard input, so it works with any map. You run it with the file: python3 main.py < map.txt.

Exercise

Step 1: the map

Read the map into a map from a crossroad to a list of streets (to which crossroad and how many minutes). A two-way street goes into the lists of both ends, a one-way street only into the list of its start. A crossroad with no outgoing streets must be in the map too, with an empty list.

Print the number of crossroads and the neighbours of the Depot, the Market and the Park, in the order of the lines in the file:

crossroads: 8
Depot: Station 4, Market 3, Stadium 16
Market: Depot 3, Square 2, Park 4
Park: Stadium 2

Solution

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


def read_map(text):
    city = {}
    for line in text.strip().splitlines():
        a, kind, b, minutes = line.split()
        add_street(city, a, b, int(minutes), kind == "-")
    return city


def neighbors(city, place):
    return f"{place}: " + ", ".join(f"{to} {m}" for to, m in city[place])


city = read_map(sys.stdin.read())
print(f"crossroads: {len(city)}")
print(neighbors(city, "Depot"))
print(neighbors(city, "Market"))
print(neighbors(city, "Park"))

At the top is import sys (later also heapq and deque).

The Park has one neighbour, the Stadium: Market -> Park is one-way and the Market is not in the Park's list.

Exercise

Step 2: fewest streets

Write fewestStreets(city, start, end): a BFS from start that stops as soon as it takes out end and returns the route as a list of crossroads. To build the route, keep for every crossroad where you came from (prev), then walk back from end and reverse the list.

fewest streets: Depot → Stadium → Hospital

Solution

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


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


city = read_map(sys.stdin.read())
print(f"fewest streets: {" → ".join(fewest_streets(city, "Depot", "Hospital"))}")

A crossroad is marked as seen when it goes into the queue, not when it comes out: otherwise one crossroad goes in several times.

Exercise

Step 3: how many minutes

Add minutesOf(city, route), which adds up the minutes of the streets along the route, and describe(city, route), which returns the route, the number of streets and the minutes. Print the route from step 2 with describe:

fewest streets: Depot → Stadium → Hospital (2 streets, 18 min)

Solution

def minutes_of(city, route):
    total = 0
    for a, b in zip(route, route[1:]):
        total += next(m for to, m in city[a] if to == b)
    return total


def describe(city, route):
    return f"{' → '.join(route)} ({len(route) - 1} streets, {minutes_of(city, route)} min)"


city = read_map(sys.stdin.read())
print(f"fewest streets: {describe(city, fewest_streets(city, "Depot", "Hospital"))}")

Two streets, but 18 minutes: sixteen of them on the ring road.

See it

Two routes on one map

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

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

Step by step, in words

The map: 8 crossroads and 10 streets with their minutes. Market → Park is one-way; the ring road from Depot to Stadium is 16 min.
BFS, one street from Depot: Station, Market, Stadium. Minutes do not matter to it.
Two streets away: Square, Park, Hospital. Hospital is already in the queue, from Stadium.
Fewest streets: Depot → Stadium → Hospital, 2 streets, but 18 min: 16 of them are the ring road.
Dijkstra: the queue is ordered by minutes. Depot 0; its neighbours go into the queue: Station 4, Market 3, Stadium 16.
The fastest in the queue is Market, 3 min. New: Square 5, Park 7.
Station, 4 min: through it nothing gets faster.
The fastest in the queue is Square, 5 min. New: Cinema 10.
Park at 7 min. Through it Stadium drops from 16 to 9.
The fastest in the queue is Stadium, 9 min. New: Hospital 11.
Cinema, 10 min: through it nothing gets faster.
Hospital comes out at 11 min: nothing left in the queue is faster, so this is the answer.
Fastest: Depot → Market → Park → Stadium → Hospital, 4 streets, 11 min.
Two answers to two questions: 2 streets and 18 min, or 4 streets and 11 min. For a courier, minutes are what count.

BFS sees only the number of streets and picks the ring road. Dijkstra takes the crossroads out by minutes and reaches the Hospital in 11 min through the Market, the one-way street and the Stadium. The Stadium first has 16 min along the ring road, then drops to 9 through the Park.

Exercise

Step 4: fastest

Write fastest(city, start, end) with Dijkstra: dist keeps the fewest minutes so far, the queue is ordered by minutes and prev keeps the route. Print both routes:

fewest streets: Depot → Stadium → Hospital (2 streets, 18 min)
fastest: Depot → Market → Park → Stadium → Hospital (4 streets, 11 min)

Solution

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


city = read_map(sys.stdin.read())
print(f"fewest streets: {describe(city, fewest_streets(city, "Depot", "Hospital"))}")
print(f"fastest: {describe(city, fastest(city, "Depot", "Hospital"))}")

heapq keeps the list as a heap. The entries are pairs (minutes, crossroad): tuples compare by the minutes first.

Try it

Fill in

A crossroad can go into the queue several times, when the minutes to it drop. The old entry stays. What does the program do when it takes it out?

if minutes > dist[at]:

Try it

Predict the way back

The courier returns from the Hospital to the Depot. The program asks fastest(city, "Hospital", "Depot"). What does it print?

city = read_map(sys.stdin.read())
print(f"back: {describe(city, fastest(city, "Hospital", "Depot"))}")

Answer

back: Hospital → Cinema → Square → Market → Depot (4 streets, 13 min)

back: Hospital → Stadium → Depot (2 streets, 18 min)

back: Hospital → Stadium → Park → Market → Depot (4 streets, 11 min)

Exercise

Step 5: the whole program

Add the way back. The whole program prints:

fewest streets: Depot → Stadium → Hospital (2 streets, 18 min)
fastest: Depot → Market → Park → Stadium → Hospital (4 streets, 11 min)
back: Hospital → Cinema → Square → Market → Depot (4 streets, 13 min)

The whole program

import heapq
import sys
from collections import deque


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


def read_map(text):
    city = {}
    for line in text.strip().splitlines():
        a, kind, b, minutes = line.split()
        add_street(city, a, b, int(minutes), kind == "-")
    return city


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


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


def minutes_of(city, route):
    total = 0
    for a, b in zip(route, route[1:]):
        total += next(m for to, m in city[a] if to == b)
    return total


def describe(city, route):
    return f"{' → '.join(route)} ({len(route) - 1} streets, {minutes_of(city, route)} min)"


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


city = read_map(sys.stdin.read())
print(f"fewest streets: {describe(city, fewest_streets(city, "Depot", "Hospital"))}")
print(f"fastest: {describe(city, fastest(city, "Depot", "Hospital"))}")
print(f"back: {describe(city, fastest(city, "Hospital", "Depot"))}")

Try it

Find the bug

A colleague has shortened addStreet. Now the way back comes out at 11 min:

back: Hospital → Stadium → Park → Market → Depot (4 streets, 11 min)

Pick the line with the bug.

See it

Measure: the city grows

A real city has thousands of crossroads. The grid is a speed test: n crossroads in a square, streets between neighbours, minutes by a formula. The courier starts at the top left corner and goes to the bottom right:

def grid_city(size):
    city = {}
    for r in range(size):
        for c in range(size):
            at = f"{r}:{c}"
            if c + 1 < size:
                add_street(city, at, f"{r}:{c + 1}", 1 + (r * 7 + c * 13) % 9, True)
            if r + 1 < size:
                add_street(city, at, f"{r + 1}:{c}", 1 + (r * 11 + c * 5) % 9, True)
    return city


city = grid_city(100)
print(f"crossroads: {len(city)}")
few = fewest_streets(city, "0:0", "99:99")
print(f"fewest streets: {len(few) - 1} streets, {minutes_of(city, few)} min")
fast = fastest(city, "0:0", "99:99")
print(f"fastest: {minutes_of(city, fast)} min")

crossroads: 10000
fewest streets: 198 streets, 990 min
fastest: 693 min

Run both algorithms in the browser. BFS looks at every street once: O(n). So does Dijkstra, but every heap entry costs O(log n): O(n log n). At n = 1000 that is 3,966 against 15,778 operations, and at n = 100,000 it is 398,158 against 2,348,779:

BFS: fewest streets O(n)
Dijkstra: fastest O(n log n)

Algorithm	n = 10	n = 1,000	n = 100,000
BFS: fewest streets	22	3,966	398,158
Dijkstra: fastest	34	15,778	2,348,779

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 fastest(city, start, end):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, at = heapq.heappop(queue)
        if minutes > dist[at]:
            continue
        if at == end:
            return route(prev, end)
        for to, length in city[at]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = at
                heapq.heappush(queue, (t, to))
    return []

More precisely, if you are curious

Dijkstra is slower, but it answers the question about minutes, and BFS cannot. Both stop as soon as they take out the target: for a nearby target they look at a small part of the city.

Navigation for whole countries does not run plain Dijkstra from every place. It preprocesses the map (contraction hierarchies, for example) and searches with A*, which adds an estimate of how far the target still is. The base is still Dijkstra.

Exercise

Road works

Solve this one in your editor.

A closed street. The Park – Stadium street is closed for road works. Give readMap a set of closed streets ("Park Stadium") that skips those lines in both directions. Print both routes from the Depot to the Hospital:

fewest streets: Depot → Stadium → Hospital (2 streets, 18 min)
fastest: Depot → Market → Square → Cinema → Hospital (4 streets, 13 min)

More tasks

Only the minutes. Write a version of fastest that returns the minutes to every crossroad without stopping at the target. Which crossroad is the farthest from the Depot?
Without a crossroad. The Square is closed for an event. How do you leave it out without touching the map?
An empty ring road. At night the ring road is empty and takes 6 min. Change the minutes in the map: which route is the fastest now, and is it the same as the BFS one?

Test

Check yourself

1. BFS and Dijkstra give different routes from the Depot to the Hospital. Which one is wrong?Dijkstra, because it takes more streetsBFS, because it is slowerNeither: BFS answers "fewest streets", Dijkstra answers "fewest minutes"

2. Why does BFS not find the fastest route in this city?Because the queue is FIFOThe streets take different minutes, and BFS counts every street as oneBecause there is a one-way street

3. In Dijkstra, the entry that comes out of the queue sometimes has more minutes than dist. What does the program do?Updates dist with the larger numberSkips it: the crossroad has already come out with fewer minutesStops

When the minutes to a crossroad drop, the program adds a new entry and the old one stays in the queue. When the old one comes out, it is stale: minutes > dist[at], and it is skipped.

4. Market -> Park is one-way. What belongs in the adjacency list?BothPark among the Market's neighbours, but not Market among the Park'sOnly Market among the Park's neighbours

5. The city is a grid with n crossroads. How does the number of operations of the two algorithms grow?Both O(n²)Both O(n)BFS O(n), Dijkstra O(n log n): the heap adds log n per street

City navigation

Cookies