← 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

🤔 What is Dijkstra's algorithm?

Dijkstra's algorithm finds the shortest path between two points in a network with weighted connections. It's used everywhere — from GPS navigation to internet routing to finding cheapest flights!

🍕 Analogy: Imagine you're in a maze where each path has a toll fee. Dijkstra's is like having a smart guide who always knows the cheapest route to any destination!
⚙️

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

There are two ways to represent a graph (network) in a computer's memory. Click to see each one for your current map:

Matrix = a grid showing the cost between every pair of locations (0 = no direct road). Good for dense graphs.
List = each location lists only its neighbours. Good for sparse graphs (fewer roads).
💡

How does it work?

Dijkstra's algorithm finds the shortest route — like a sat-nav working out directions.

  1. Start at your chosen location. It costs 0 to be here. Everywhere else starts as "unknown" (∞)
  2. Look around: Check all roads from where you are
  3. If cheaper route found — update the cost and remember how you got there
  4. Mark as "done" — cheapest way here is confirmed
  5. Move to cheapest unvisited location and repeat
  6. Stop when you reach the destination!
Speed
O((V+E) log V)
Memory
O(V)
📝

Exam Tips