Explore modules

Dijkstra's Algorithm

Finding the shortest path in a weighted graph by greedily exploring the nearest unvisited node.

Free theory article

Finding the shortest path in a weighted graph by greedily exploring the nearest unvisited node.

Concept & interpretation

Dijkstra's algorithm computes shortest-path distances from a source vertex s to all vertices in a graph with non-negative edge weights. By repeatedly extracting the unvisited vertex u with the smallest tentative distance d[u] and relaxing its outgoing edges, the algorithm maintains the invariant that every settled vertex has achieved its true minimum path cost.

Interactive Experiment: What to Enter and Observe

Open the Dijkstra's Algorithm module to step through vertex extraction and edge relaxation:

  1. Set the Nodes slider to 6 for a compact graph where every edge weight and tentative distance label d=... is easy to inspect.
  2. Click Step once to initialize source vertex 0 (green) at d=0, then click Step again and predict which blue queued neighbor has the minimum tentative distance before it turns purple as the current vertex.
  3. Continue clicking Step (or click Run) until the algorithm finishes. Compare the amber highlighted shortest path against the Shortest path and Total weight values in the Status panel.
  4. Click a different node on the canvas to reassign the red Target (or Shift+click to change the green Source), then press Run to see how the shortest path tree adapts on the same weighted graph.
Read the full free theory article