Dijkstra's Algorithm: Shortest Path Explorer

Follow Dijkstra's algorithm as it discovers the shortest paths from a source node across a weighted graph. Each step highlights the active line of pseudocode, the current node under consideration, the frontier held in the priority queue, and how tentative distances tighten as better routes are found.

Pseudocode

  1. function dijkstra(graph, source)
  2. for each vertex v: set dist[v] to ∞
  3. set dist[source] to 0
  4. push (0, source) onto priority queue
  5. while priority queue is not empty:
  6.   (d, u) ← extract-min from queue
  7.   if d > dist[u]: continue
  8.   for each neighbor v of u with weight w:
  9.     if dist[u] + w < dist[v]:
  10.       update dist[v]
  11.       insert (dist[v], v) into queue
  12. return dist

Graph Exploration

current node in priority queue settled shortest path
Press Play or Step Forward to begin the walk-through.

Tentative Distances

    Priority Queue (min distance first)