Card 07/ 08
Practice: The Fewest Buses Between Two Stops
Five bus lines share some stops: find the fewest buses from the market to the harbour, and see why the obvious graph answers a different question.
Which thing becomes a vertex decides what a search counts. A town has five bus lines, each running both ways along its stops. Line A: Market, Mill, Pier, Dock, Quay. Line B: Quay, Harbour. Line C: Market, Park. Line D: Park, Station. Line E: Station, Harbour. A traveller at the Market wants to reach the Harbour taking as few buses as possible, changing only at a stop two lines share. What is the fewest number of buses, and what graph finds it?
Show the answer and a solution
2 buses: line A to the Quay, then line B. The obvious graph, with stops as vertices and an edge between consecutive stops on a line, counts stops passed: its shortest route, Market, Park, Station, Harbour, passes 3 stops but takes 3 buses. To count buses, make each line a vertex and join two lines when they share a stop; a breadth-first search from every line serving the start, stopping at the first line serving the end, counts buses.
| Model | Vertex | Edge | Answer | What it counts |
|---|---|---|---|---|
| Stops | A stop | Consecutive stops on a line | Market, Park, Station, Harbour | Stops passed: 3, on 3 buses |
| Lines | A line | Two lines sharing a stop | A then B | Buses: 2, passing 5 stops |
The listing searches both graphs. In the lines model every line that serves the Market starts in the queue, as in a search from many sources.
from collections import deque
lines = {
"A": ["Market", "Mill", "Pier", "Dock", "Quay"],
"B": ["Quay", "Harbour"],
"C": ["Market", "Park"],
"D": ["Park", "Station"],
"E": ["Station", "Harbour"],
}
START, END = "Market", "Harbour"
def fewest_buses() -> list[str]:
parent: dict[str, str | None] = {line: None for line, stops in lines.items() if START in stops}
queue = deque(parent)
while queue:
line = queue.popleft()
if END in lines[line]:
route = [line]
while (previous := parent[route[-1]]) is not None:
route.append(previous)
return route[::-1]
for other, stops in lines.items():
if other not in parent and set(stops) & set(lines[line]):
parent[other] = line
queue.append(other)
return []
def fewest_stops() -> list[str]:
neighbours: dict[str, list[str]] = {}
for stops in lines.values():
for here, there in zip(stops, stops[1:]):
neighbours.setdefault(here, []).append(there)
neighbours.setdefault(there, []).append(here)
parent: dict[str, str | None] = {START: None}
queue = deque([START])
while queue:
stop = queue.popleft()
for other in neighbours[stop]:
if other not in parent:
parent[other] = stop
queue.append(other)
route = [END]
while (previous := parent[route[-1]]) is not None:
route.append(previous)
return route[::-1]
def line_between(here: str, there: str) -> str:
return next(line for line, stops in lines.items() if here in stops and there in stops)
buses = fewest_buses()
print("lines as vertices:", " then ".join(buses), f"({len(buses)} buses)")
stop_route = fewest_stops()
used = [line_between(a, b) for a, b in zip(stop_route, stop_route[1:])]
print("stops as vertices:", " -> ".join(stop_route), f"({len(stop_route) - 1} stops passed, buses {' '.join(used)})")
print("the 2-bus route passes", len(lines["A"]) - 1 + len(lines["B"]) - 1, "stops")lines as vertices: A then B (2 buses)
stops as vertices: Market -> Park -> Station -> Harbour (3 stops passed, buses C D E)
the 2-bus route passes 5 stopsFor L lines, building the line graph compares pairs of lines, O(L² · s) for lines of up to s stops, or less with a map from each stop to its lines; the search over L vertices then costs little. Both models are correct graphs; only one asks the question that was posed.
← → move through sections and cards