Dijkstra's Algorithm Visualizer

Visualize how Dijkstra's algorithm finds the shortest path between nodes in a weighted graph. Draw your own graph, set edge weights, and watch the algorithm explore step by step.

Visualize Dijkstra's Algorithm

How It Works

Dijkstra's algorithm is a greedy algorithm that finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. It was conceived by computer scientist Edsger W. Dijkstra in 1956.

The algorithm maintains a set of unvisited nodes and a distance table. It repeatedly selects the unvisited node with the smallest known distance, visits it, and updates the distances of its neighbors. This process continues until the destination node is visited or all reachable nodes have been explored.

  1. 1

    Initialize the source node distance to 0 and all others to infinity

  2. 2

    Add the source node to a priority queue

  3. 3

    Extract the node with the minimum distance from the queue

  4. 4

    For each neighbor, calculate the tentative distance through the current node

  5. 5

    If the new distance is shorter, update it and add the neighbor to the queue

  6. 6

    Repeat until the destination is reached or the queue is empty

Key Properties

Time Complexity

O((V + E) log V) with a binary heap priority queue, where V is vertices and E is edges.

Weighted Graphs

Designed for graphs with non-negative edge weights. For negative weights, use Bellman-Ford instead.

Optimal Paths

Guarantees the shortest path between the source and every reachable node in the graph.

Greedy Strategy

Always processes the closest unvisited node first, building up shortest paths incrementally.

Common Use Cases

  • GPS navigation — finding the fastest route between two locations
  • Network routing protocols — OSPF uses Dijkstra's to compute shortest paths
  • Game AI pathfinding — navigating NPCs through weighted terrain and obstacle maps

Frequently Asked Questions

What is Dijkstra's algorithm?
Dijkstra's algorithm is a greedy graph algorithm that finds the shortest path from a single source node to all other nodes in a weighted graph with non-negative edge weights. It works by repeatedly selecting the unvisited node with the smallest known distance and updating its neighbors.
What is the time complexity of Dijkstra's algorithm?
With a binary heap priority queue, Dijkstra's algorithm runs in O((V + E) log V) time, where V is the number of vertices and E is the number of edges. Using a Fibonacci heap improves this to O(E + V log V).
Can Dijkstra's algorithm handle negative edge weights?
No. Dijkstra's algorithm requires all edge weights to be non-negative. For graphs with negative weights, use the Bellman-Ford algorithm instead, which can also detect negative-weight cycles.
What is the difference between Dijkstra's and BFS?
BFS finds the shortest path in unweighted graphs by exploring level by level. Dijkstra's generalizes this to weighted graphs by using a priority queue to always process the closest unvisited node, accounting for varying edge costs.

Ready to see it in action?

Open the Visualizer