Skip to content
← Back to algorithms

Step 0 / 0 · Comparisons: 0 · Swaps: 0

How this algorithm works

How it works

  1. Initialize distances to all nodes as infinity, except source = 0.
  2. Use a min-priority queue ordered by distance.
  3. Extract the node with the smallest known distance.
  4. For each neighbor, check if a shorter path is found through the current node.
  5. If yes, update the distance and add to the priority queue.
  6. Mark the node as visited (finalized).
  7. Repeat until all nodes are visited or the target is reached.

Key concepts

  • Greedy algorithm
  • Shortest path (single source)
  • Requires non-negative edge weights
  • Priority queue / min-heap for efficiency

When to use it

Finding shortest paths in graphs with non-negative weights. Used in GPS navigation, network routing, and game AI pathfinding.

Did you know

Named after Edsger Dijkstra, who invented it in 1956 in 20 minutes while shopping with his fiancée.