← Back to all tools

πŸ—ΊοΈ Find the Shortest Route

Using Dijkstra's Algorithm

This is how Google Maps finds the fastest way to your destination. Build a map of locations and roads, then watch the computer find the cheapest route step by step.

CS GCSE Β§1.3.1 CS A-Level Unit 1 CS A-Level Unit 3
βš™οΈ

Controls

Not yet checked
Waiting to check
Checking now
Done
Shortest route
πŸ‘‹ A map is already loaded! Choose a start and end location above, then click β–Ά Find Route to watch the algorithm find the shortest path. Or click ⏭ Step to go one step at a time.
Choose a start and end location, then click β–Ά Find Route.
πŸ“Š

Distance Table

LocationCostCame fromStatus
πŸ“‹

Graph Representation CS A-Level Unit 3

πŸ’‘

How does it work?

Dijkstra's algorithm is how computers find the shortest route β€” like a sat-nav working out directions.

  1. Start at your chosen location. It costs 0 to be where you already are. Every other place starts as "unknown" (∞ means "we don't know yet")
  2. Look around: Check all the roads from where you are. Calculate the total cost to reach each neighbour
  3. If you found a cheaper route to a neighbour, update its cost and remember how you got there
  4. Mark this location as "done" β€” you've found the cheapest way to get here
  5. Move to the unvisited location with the lowest cost and repeat
  6. Stop when you reach the destination!
Speed
O((V+E) log V)
Slows as the map grows
Memory
O(V)
Stores cost per location