Skip to content
Tutorials Center
My learning

Topics

Lesson 213 of 225 ยท Projects

Project: Route Planner

Build a route planner on a city map in stages. Model the roads as a graph, find fewest roads with BFS, shortest distance with Dijkstra, then speed up with A*.

Every map application answers the same question: what is the best way to get from here to there? In this project you will build a small route planner from scratch. Along the way you will reuse most of the graph toolbox from the previous chapters: a graph representation, breadth-first search, Dijkstra's algorithm, and finally A*, the algorithm that powers most real navigation and game pathfinding.

We will build the planner in stages, and every stage is a complete, runnable program. By the end you will have a RoutePlanner that prints turn-by-turn style routes, handles missing roads and unreachable cities, and has been tested against a simpler algorithm to prove it is right.

The map

Our fictional country has twelve towns, each at an (x, y) position on a 100 by 100 grid, joined by two-way roads. A road's length is the straight-line distance between its two towns rounded up to a whole number, plus an optional detour for winding roads. That detail matters later: because a road can never be shorter than the straight line between its ends, the straight-line distance is a safe underestimate for A*.

TEXT
 y
100 โ”ค
    โ”‚      Brook(20,70)     Eastwick(45,85)
    โ”‚            \           /       Hollin(70,75)
    โ”‚   Aldport   Dunmere(40,55)---Garrow(62,50)---Jorvik(88,60)
    โ”‚   (5,50)       |                |                |
    โ”‚            Cairn(22,30)    Fenwood(48,20)    Kelby(95,35)
    โ”‚                               \  Ivel(75,25)  /
    โ”‚                              Lowmoor(60,10)
    โ””โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€ x
 (a sketch, not to scale)

Stage 1: the graph and fewest roads

We store the map as an adjacency dictionary: graph[town] maps each neighbor to the road length. Roads are two-way, so we record each road in both directions. Then BFS finds the route with the fewest roads, which is the shortest path when every edge counts as 1.

Python Stage 1: the map and a BFS route

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

BFS found a route with the fewest roads, but "few roads" is not the same as "short". It does not look at lengths at all, and a route with fewer roads can easily be much longer in kilometers. We need weights.

Stage 2: shortest distance with Dijkstra

Dijkstra's algorithm always expands the unfinished town with the smallest distance from the start, using a min-heap to find it. When it first pops a town, that distance is final (this works because all lengths are non-negative). We also record each town's parent so we can rebuild the path, and we count expansions (towns finalized) to compare algorithms later.

Python Stage 2: Dijkstra with path reconstruction

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The heap may hold several entries for one town (we push again whenever we find a shorter way), so we skip stale ones when popped: the standard "lazy deletion" approach. With V towns and E roads this runs in O((V + E) log V).

Stage 3: A*, searching toward the goal

Dijkstra explores outward in a circle around the start, in every direction equally, even away from the destination. We can do better because we have extra knowledge: the map coordinates tell us roughly which direction the goal lies in.

A* orders the heap by f = g + h, where g is the known distance from the start and h is a heuristic: an estimate of the remaining distance to the goal. Here h is the straight-line distance. Towns that are close to the start and point toward the goal come out first.

TEXT
Dijkstra from S:          A* from S toward G:
   . . o o o . .             . . . . . . .
   . o o o o o .             . . . o o . .
   . o o S o o o G           . . . S o o o G    (o = expanded)
   . o o o o o .             . . . o o . .
   . . o o o . .             . . . . . . .

A* is only guaranteed correct if the heuristic is admissible (never overestimates the true remaining distance). Our straight-line distance qualifies because every road is at least as long as the straight line, and it is also consistent, so a town never needs to be re-expanded.

Python Stage 3: A* versus Dijkstra

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A* always returns the same distance as Dijkstra, but usually expands fewer towns, because it ignores directions that lead away from the goal. On a twelve-town map the saving is modest, yet on a real road network with millions of intersections it is the difference between instant and slow. Note that h = 0 turns A* into Dijkstra, so one function serves both.

An overestimating heuristic breaks A*. If h can be larger than the true remaining distance, A* may return a path that is not the shortest. Using road length in kilometers as h for a map whose weights are travel minutes is a classic way to get this wrong. Always make sure the heuristic uses the same units as the edge weights and never exceeds the truth.

Stage 4: the finished planner

Now we wrap everything in a RoutePlanner class with the features an application needs: closing roads (for example, for repairs), clear errors for unknown towns, a friendly report for unreachable destinations, and readable output with the running distance.

Python Stage 4: the RoutePlanner class

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Stage 5: prove it with a test

A* is easy to get subtly wrong, so we test it the way the autocomplete project did: compare it with a simpler, trusted algorithm on many inputs. Here we generate random maps (random points, roads between nearby ones, lengths never shorter than the straight line) and check that A*, Dijkstra and a slow reference, the Bellman-Ford algorithm, agree on every distance:

Python Stage 5: A* versus Dijkstra versus Bellman-Ford

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The test includes unreachable pairs too (all three return None there), which is where many path-finding bugs hide.

Complexity

With V towns and E roads: BFS is O(V + E) but ignores lengths; Dijkstra with a binary heap is O((V + E) log V); A* has the same worst case but expands far fewer nodes in practice when the heuristic is informative, and degrades to Dijkstra when it is not. All three use O(V) extra space for distances, parents and the heap.

Ideas to extend it

  • Travel time instead of distance. Give each road a speed limit; the heuristic then becomes straight-line distance divided by the maximum speed.
  • Turn costs and one-way streets. Use a directed graph, or make "road plus direction" the node.
  • Many queries on one map. Precompute with landmarks (ALT) or contraction hierarchies, as production routers do. See shortest-path variants.
  • Multiple stops. Visiting every town once is the travelling salesman problem, much harder than a single route.
  • Grids. On a grid map, use the Manhattan distance heuristic for 4-way movement.

Common mistakes

  • Using BFS on weighted edges. BFS only counts roads. Use Dijkstra or A* once lengths differ.
  • Stopping when the goal is first pushed. Stop when it is first popped; a shorter route may still be waiting in the heap.
  • A heuristic that overestimates. This silently returns non-optimal routes.
  • Negative edge weights with Dijkstra. Dijkstra's finality argument breaks; use Bellman-Ford.
  • Forgetting stale heap entries. Without the done check you re-expand towns and waste time (and may report wrong counts).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does BFS not always give the shortest driving distance?

    BFS treats every road as cost 1, so it minimizes the number of roads. A route with fewer roads can be much longer in distance.
  2. 2. In A*, what does the heap order towns by?

    f = g + h combines the known cost so far with an optimistic estimate of the remaining cost, so promising towns are expanded first.
  3. 3. What makes a heuristic admissible?

    An admissible heuristic is optimistic. With one that never overestimates, A* is guaranteed to return an optimal path.
  4. 4. What happens if you use h = 0 for every town in A*?

    With h = 0, f equals g, so towns are expanded in order of distance from the start, which is Dijkstra.
  5. 5. Why should the search stop when the goal is popped from the heap, not when it is pushed?

    A shorter route to the goal can be found later through another town. When the goal is popped, no unfinished town can offer a better route.

Summary

  • Model roads as an adjacency dictionary of neighbor to length; keep coordinates separately for heuristics.
  • BFS gives the fewest roads, Dijkstra gives the shortest distance with non-negative weights, and A* adds a heuristic to search toward the goal.
  • A* orders by f = g + h and is optimal when h is admissible (never overestimates); h = 0 is Dijkstra.
  • Use a heap with lazy deletion, rebuild the path from parent pointers, and stop when the goal is popped.
  • Test with randomized comparisons against simpler algorithms, including unreachable cases.

Next: Project: Text Editor Buffer with Undo