When an ambulance is dispatched, "is there a route?" is only half the question. The real question is: what is the shortest route that avoids everything that is blocked right now? An accident, a construction zone or a flooded underpass can turn the usual route into a dead end.
I built SwiftRoute, a small Python prototype that models a city as a grid and finds the shortest valid ambulance-to-hospital route using Breadth-First Search (BFS). This post covers the problem, why BFS is the right tool, the code, four test cases, the complexity analysis, and benchmarks against DFS, Dijkstra and A*.
1. The routing problem
The city is a 2D grid. Each cell is an intersection, and the ambulance can move one cell up, down, left or right. Every move costs the same.
| Description | |
|---|---|
| Input 1 |
grid: an M x N matrix where 0 = open road and 1 = roadblock |
| Input 2 |
start: the ambulance's (row, col)
|
| Input 3 |
end: the hospital's (row, col)
|
| Output | The shortest valid path as a list of (row, col) coordinates, plus a visual of the route. If the hospital cannot be reached, the program returns None and raises a "No valid road route" alert. |
Assumptions: all road segments are equal length (unweighted), moves are 4-directional, and the grid is a snapshot of current road conditions.
2. The algorithm: Breadth-First Search
BFS explores the grid in rings, like ripples spreading from a stone dropped at the ambulance's position. It uses a FIFO queue:
- Put the start cell in the queue.
- Take the oldest cell out. If it is the hospital, stop.
- Otherwise, add every open, unseen neighbour to the queue and remember which cell it came from (its parent).
- Repeat. When the hospital is found, follow the parents backwards to rebuild the route.
Here is the distance from the ambulance to every reachable cell in Test Case 1 below (# is a roadblock). BFS discovers cells in exactly this order, from distance 0 outward:
0 # 6 7 8
1 # 5 # 9
2 3 4 # 10
3 # # # 9
4 5 6 7 8
The hospital sits in the top-right corner at distance 8.
Why BFS finds the shortest path: because the queue is first-in, first-out, BFS processes every cell at distance d before any cell at distance d + 1. So the first time it reaches the hospital, it has done so in the fewest possible moves.
3. Why BFS, and how it compares
| Algorithm | Finds the shortest path (unweighted)? | Time | Verdict for this problem |
|---|---|---|---|
| BFS | Yes, guaranteed | O(M x N) |
Best fit. Simplest, and optimal for equal-cost moves. |
| DFS | No | O(M x N) |
Finds a route, often a long winding one. Unsafe for emergency use. |
| Dijkstra | Yes | O(M x N x log(M x N)) |
Needed only when roads have different costs. On an unweighted grid it does BFS's work plus a priority-queue overhead. |
| A* | Yes (with Manhattan heuristic) |
O(M x N) worst case, usually far less |
Explores fewer cells by steering toward the goal. A strong upgrade for large maps (see the results in section 7). |
4. The prototype
The core is one function, find_shortest_path. The parent dictionary does double duty: it records how to rebuild the route and acts as the visited set that prevents infinite loops. Invalid input (start or end on a roadblock or outside the grid) raises an error instead of returning nonsense.
Save this as swiftroute.py:
"""SwiftRoute: BFS-based ambulance routing on a city grid."""
import sys
from collections import deque
OPEN, BLOCKED = 0, 1
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)] # up, down, left, right
def find_shortest_path(grid, start, end):
"""Return (path, expanded).
path -- list of (row, col) from start to end, or None if unreachable
expanded -- how many cells BFS took off the queue before stopping
"""
rows, cols = len(grid), len(grid[0])
def is_open(cell):
r, c = cell
return 0 <= r < rows and 0 <= c < cols and grid[r][c] == OPEN
if not is_open(start) or not is_open(end):
raise ValueError("Start and end must be on open road cells inside the grid.")
queue = deque([start])
parent = {start: None} # doubles as the visited set
expanded = 0
while queue:
current = queue.popleft()
expanded += 1
if current == end: # hospital reached
break
for dr, dc in DIRECTIONS:
nxt = (current[0] + dr, current[1] + dc)
if is_open(nxt) and nxt not in parent:
parent[nxt] = current
queue.append(nxt)
if end not in parent: # queue emptied without ever reaching the hospital
return None, expanded
path, node = [], end
while node is not None: # walk parents back from hospital to ambulance
path.append(node)
node = parent[node]
path.reverse()
return path, expanded
def print_city_grid(grid, start, end, path=None):
on_path = set(path or [])
for r, row in enumerate(grid):
line = []
for c, cell in enumerate(row):
if (r, c) == start:
line.append("π")
elif (r, c) == end:
line.append("π₯")
elif cell == BLOCKED:
line.append("π§")
elif (r, c) in on_path:
line.append("π©")
else:
line.append("β¬")
print(" ".join(line))
def run_case(title, grid, start, end):
print(f"\n=== {title} ===")
try:
path, expanded = find_shortest_path(grid, start, end)
except ValueError as err:
print(f"INPUT ERROR: {err}")
return
print_city_grid(grid, start, end, path)
if path is None:
print("ALERT: No valid road route to the hospital. Dispatch helicopter.")
else:
print(f"Route length : {len(path) - 1} moves")
print(f"Cells expanded: {expanded}")
print(f"Path : {path}")
if __name__ == "__main__":
if hasattr(sys.stdout, "reconfigure"): # keep emojis safe on Windows consoles
sys.stdout.reconfigure(encoding="utf-8")
# 0 = open road, 1 = roadblock
city = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0],
]
ambulance, hospital = (0, 0), (0, 4)
run_case("TEST 1: Normal route", city, ambulance, hospital)
# Accident at (2, 1) closes the short route -> BFS must find a detour
city_accident = [row[:] for row in city]
city_accident[2][1] = 1
run_case("TEST 2: Accident forces a detour", city_accident, ambulance, hospital)
# Second accident at (4, 2) seals the last route -> hospital unreachable
city_sealed = [row[:] for row in city_accident]
city_sealed[4][2] = 1
run_case("TEST 3: Hospital cut off", city_sealed, ambulance, hospital)
# Bad input: ambulance placed on a roadblock
run_case("TEST 4: Invalid start cell", city, (0, 1), hospital)
5. Test cases
All four tests use the same 5x5 city, so you can watch the route change as roads close. π = ambulance, π₯ = hospital, π§ = roadblock, π© = route, β¬ = unused open road.
Test 1: Normal route
=== TEST 1: Normal route ===
π π§ π© π© π₯
π© π§ π© π§ β¬
π© π© π© π§ β¬
β¬ π§ π§ π§ β¬
β¬ β¬ β¬ β¬ β¬
Route length : 8 moves
Cells expanded: 15
Path : [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 3), (0, 4)]
The grid has 7 roadblocks. Two routes exist: an 8-move route through the middle and a 12-move route around the outside. BFS returns the 8-move one.
Test 2: An accident forces a detour
An accident closes the intersection at (2, 1), which was part of the short route.
=== TEST 2: Accident forces a detour ===
π π§ β¬ β¬ π₯
π© π§ β¬ π§ π©
π© π§ β¬ π§ π©
π© π§ π§ π§ π©
π© π© π© π© π©
Route length : 12 moves
Cells expanded: 13
Path : [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (3, 4), (2, 4), (1, 4), (0, 4)]
BFS reroutes along the outer roads: 12 moves instead of 8. The route is longer, but it is still the shortest one that is actually drivable.
Test 3: The hospital is cut off
A second accident at (4, 2) seals the last remaining road.
=== TEST 3: Hospital cut off ===
π π§ β¬ β¬ π₯
β¬ π§ β¬ π§ β¬
β¬ π§ β¬ π§ β¬
β¬ π§ π§ π§ β¬
β¬ β¬ π§ β¬ β¬
ALERT: No valid road route to the hospital. Dispatch helicopter.
BFS exhausts the six cells the ambulance can reach, confirms the hospital is not among them, and stops cleanly with an alert. It does not loop forever, and it does not return a fake route.
Test 4: Invalid input
The ambulance is placed on a roadblock at (0, 1).
=== TEST 4: Invalid start cell ===
INPUT ERROR: Start and end must be on open road cells inside the grid.
Bad input is rejected with a clear message instead of producing a misleading route.
6. Complexity analysis
Let the grid have M rows and N columns, so there are V = M x N cells.
-
Time:
O(V + E) = O(M x N). Each cell is added to the queue at most once, and each cell checks at most 4 neighbours, soE <= 4 x M x N. In the worst case (hospital unreachable or in the far corner), BFS touches every cell once.deque.popleft()isO(1), so the queue never adds extra cost. -
Space:
O(M x N). Theparentdictionary can hold one entry per cell. The queue holds only the current frontier, which is smaller.
7. Experimental results
I wrote a benchmark script (full code in the appendix) that runs two experiments. Each timing is the median of 5 runs.
Tested on: TODO (your CPU, RAM, Python version. The script prints the CPU and Python version on its first line.)
Experiment 1: does BFS scale linearly?
An open n x n grid with the ambulance in one corner and the hospital in the opposite corner, which is close to BFS's worst case because it has to expand every cell.
| Grid | Cells | Cells expanded | Time (ms) | Time per cell (Β΅s) |
|---|---|---|---|---|
| 50x50 | 2,500 | 2,500 | TODO | TODO |
| 100x100 | 10,000 | 10,000 | TODO | TODO |
| 200x200 | 40,000 | 40,000 | TODO | TODO |
| 400x400 | 160,000 | 160,000 | TODO | TODO |
| 800x800 | 640,000 | 640,000 | TODO | TODO |
Each step multiplies the number of cells by 4. If BFS really is O(M x N), the time should grow by roughly 4x per row and the time per cell should stay roughly constant. TODO: write one sentence on what your numbers show.
Experiment 2: BFS vs DFS vs Dijkstra vs A*
A 200x200 grid with 25% randomly placed roadblocks (fixed random seed 3 so it is reproducible), ambulance at the top-left and hospital at the bottom-right.
| Algorithm | Route length (moves) | Cells expanded | Time (ms) |
|---|---|---|---|
| BFS | 398 | 29,848 | TODO |
| DFS | 1200 | 1,530 | TODO |
| Dijkstra | 398 | 29,848 | TODO |
| A* (Manhattan) | 398 | 9,882 | TODO |
What the deterministic columns show:
- DFS is the trap. It expanded the fewest cells but returned a route about 3x longer than optimal (1200 vs 398 moves). Being fast to finish is worthless when the route it returns is three times the driving distance.
- BFS and Dijkstra find identical optimal routes, with identical cell counts, because all roads cost the same. Dijkstra just does it with extra priority-queue work.
- A* expanded only about a third of the cells (9,882 vs 29,848) while still finding an optimal route, because the Manhattan-distance heuristic keeps it pointed at the hospital. Its per-cell cost is higher than BFS's, so the saving in wall-clock time is smaller than the saving in cells. TODO: add one sentence on what your timings show.
8. Limitations and where this could go
- Real roads are not unweighted. Speed limits, traffic and one-way streets make edge costs differ. The natural upgrade is Dijkstra or A* on a weighted graph, as the experiment above suggests.
- Live conditions. SwiftRoute treats the grid as a snapshot. A real system would re-run the search when a new roadblock is reported.
- Multiple hospitals. Starting BFS from all hospitals at once (multi-source BFS) would give the nearest hospital in a single pass.
- Scale. Python dictionaries are convenient but memory-hungry. This implementation is fine for the grid sizes tested here, but a city-scale map would need a compact graph representation, and probably a compiled language.
9. Conclusion
For an unweighted routing problem, BFS is simple, provably optimal and linear in the size of the map. The tests show it handles normal routing, detours, unreachable hospitals and bad input, and the benchmarks show why it beats DFS on correctness and why A* is the next step when maps get big.
Appendix: benchmark code
Save this as benchmark.py in the same folder as swiftroute.py, then run python benchmark.py. It prints both tables in Markdown.
"""Benchmarks for SwiftRoute: (1) BFS scaling, (2) BFS vs DFS vs Dijkstra vs A*."""
import heapq
import platform
import random
import statistics
import time
from swiftroute import DIRECTIONS, OPEN, find_shortest_path
def neighbours(grid, cell):
rows, cols = len(grid), len(grid[0])
for dr, dc in DIRECTIONS:
r, c = cell[0] + dr, cell[1] + dc
if 0 <= r < rows and 0 <= c < cols and grid[r][c] == OPEN:
yield (r, c)
def rebuild(parent, end):
path, node = [], end
while node is not None:
path.append(node)
node = parent[node]
return path[::-1]
def dfs(grid, start, end):
stack, parent, expanded = [(start, None)], {}, 0
while stack:
cell, prev = stack.pop()
if cell in parent:
continue
parent[cell] = prev
expanded += 1
if cell == end:
return rebuild(parent, end), expanded
for nxt in neighbours(grid, cell):
if nxt not in parent:
stack.append((nxt, cell))
return None, expanded
def dijkstra(grid, start, end):
dist, parent, expanded = {start: 0}, {start: None}, 0
heap, done = [(0, start)], set()
while heap:
d, cell = heapq.heappop(heap)
if cell in done:
continue
done.add(cell)
expanded += 1
if cell == end:
return rebuild(parent, end), expanded
for nxt in neighbours(grid, cell):
if d + 1 < dist.get(nxt, float("inf")):
dist[nxt], parent[nxt] = d + 1, cell
heapq.heappush(heap, (d + 1, nxt))
return None, expanded
def a_star(grid, start, end):
h = lambda p: abs(p[0] - end[0]) + abs(p[1] - end[1]) # Manhattan distance
g, parent, expanded = {start: 0}, {start: None}, 0
heap, done = [(h(start), start)], set()
while heap:
_, cell = heapq.heappop(heap)
if cell in done:
continue
done.add(cell)
expanded += 1
if cell == end:
return rebuild(parent, end), expanded
for nxt in neighbours(grid, cell):
if g[cell] + 1 < g.get(nxt, float("inf")):
g[nxt], parent[nxt] = g[cell] + 1, cell
heapq.heappush(heap, (g[nxt] + h(nxt), nxt))
return None, expanded
def median_ms(fn, *args, runs=5):
times = []
for _ in range(runs):
t0 = time.perf_counter()
result = fn(*args)
times.append((time.perf_counter() - t0) * 1000)
return statistics.median(times), result
def random_city(n, block_rate, seed):
rng = random.Random(seed)
grid = [[1 if rng.random() < block_rate else 0 for _ in range(n)] for _ in range(n)]
grid[0][0] = grid[n - 1][n - 1] = 0
return grid
if __name__ == "__main__":
print(f"Machine: {platform.processor() or platform.machine()} | Python {platform.python_version()}\n")
print("### Experiment 1: BFS scaling (open n x n grid, corner to corner)\n")
print("| Grid | Cells | Cells expanded | Time (ms) | Time per cell (Β΅s) |")
print("|---|---|---|---|---|")
for n in (50, 100, 200, 400, 800):
grid = [[0] * n for _ in range(n)]
ms, (path, expanded) = median_ms(find_shortest_path, grid, (0, 0), (n - 1, n - 1))
print(f"| {n}x{n} | {n*n:,} | {expanded:,} | {ms:.2f} | {ms * 1000 / (n*n):.2f} |")
n, rate, seed = 200, 0.25, 3
grid = random_city(n, rate, seed)
start, end = (0, 0), (n - 1, n - 1)
print(f"\n### Experiment 2: algorithm comparison ({n}x{n} grid, {int(rate*100)}% roadblocks, seed {seed})\n")
print("| Algorithm | Route length (moves) | Cells expanded | Time (ms) |")
print("|---|---|---|---|")
for name, fn in (("BFS", find_shortest_path), ("DFS", dfs), ("Dijkstra", dijkstra), ("A* (Manhattan)", a_star)):
ms, (path, expanded) = median_ms(fn, grid, start, end)
length = "no path" if path is None else len(path) - 1
print(f"| {name} | {length} | {expanded:,} | {ms:.2f} |")
Top comments (0)