Dijkstra's Shortest Path

Step through the algorithm and watch the distance table update when a shorter path is found

Speed: 700ms
Unvisited
Current node
Exploring edge
Distance updated
Visited / shortest path
Press Step or Play to begin Dijkstra's algorithm from node A

Distance Tracking Table

How Dijkstra's Algorithm Works

Dijkstra's algorithm finds the shortest path from a source node to every other node in a weighted graph. It works by always processing the unvisited node with the smallest known distance.

set distance[source] = 0, all others = ∞
while there are unvisited nodes:
  current = unvisited node with smallest distance
  mark current as visited
  for each unvisited neighbour of current:
    newDist = distance[current] + edge weight
    if newDist < distance[neighbour]: // shorter path found!
      distance[neighbour] = newDist // update distance
      previous[neighbour] = current // remember the path

Key insight: A node's distance may be updated multiple times before it is visited. Each update means a shorter path was found through a different route. Once a node is visited, its shortest distance is finalised and never changes.

Time complexity: O(V²) with a simple array, or O((V + E) log V) with a priority queue, where V = vertices and E = edges.