Skip to content
Back to AlgorithmsAll lessons

Algorithms

Dijkstra's Shortest Path

O(V²) time with this simple version, where V is the number of points and you scan all of them each round · O(V) space for the distances. A priority queue speeds this up to O((V + E) log V) on large graphs.

The idea, in plain English

Dijkstra's algorithm is a road-trip planner that always drives to the closest unvisited city next. From each city, it asks: is it cheaper to reach my neighbors through here than the best way I already knew? It only works when every road's distance is zero or positive. There can be no roads that pay you to drive them.

How it works

  1. 1Set the distance to the starting point at 0, and every other point as 'unknown' (treated as infinity) for now.
  2. 2Repeatedly pick the unvisited point with the smallest known distance, and mark it as visited.
  3. 3Check its neighbors: if reaching a neighbor through this point is shorter than what you knew before, update it. This step is called 'relaxing' the neighbor. Repeat until you visit every reachable point.

When you'd use it

Use it to find shortest paths in a graph, a network of points and connections, where connection costs are never negative — GPS route planning, network routing, or any 'cheapest way from A to B' problem.

Common beginner mistakes

  • Using it on a graph with negative connection costs. Dijkstra assumes distances only ever grow, and gives wrong answers otherwise.
  • Forgetting to mark points as visited once you settle them, which wastes time re-checking them.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Distances from A: A:0 B:3 C:1 D:4

Note: The distances come out as plain whole numbers here, because every connection cost is a whole number. There are no decimals to worry about matching between languages.

See it in motion

Watch it settleDijkstra's shortest pathfrom AO(V²) time with this simple version, where V is the number of points and you scan all of them each round · O(V) space for the distances. A priority queue speeds this up to O((V + E) log V) on large graphs.
41215A0B∞C∞D∞
Priority queuenearest out first ↤
A:0
Settled order
—

Start at A: its distance is 0, every other node is ∞ (unknown).

0/4
Settled
1
In queue
0
Updates
0.0s
Time
Settling nowIn queue / updatedFinalizedUnreached

Not sure this is the right topic? See the learning paths → or where this leads →