Dijkstra's Algorithm Step by Step

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a single source node to all other nodes in a weighted graph with non-negative edge weights. It is one of the most important algorithms in computer science and networking.

How Dijkstra's Works

1. Initialize — Set the distance of the source node to 0 and all others to infinity. Add all nodes to an unvisited set.
2. Select — Pick the unvisited node with the smallest tentative distance. This is the current node.
3. Relax neighbors — For each neighbor of the current node, calculate the distance through the current node. If it is less than the previously recorded distance, update it.
4. Mark visited — Remove the current node from the unvisited set.
5. Repeat — Continue until all reachable nodes are visited.

Initial:  A=0, B=∞, C=∞, D=∞
Visit A:  B=4, C=2, D=∞     (via A→B=4, A→C=2)
Visit C:  B=3, D=7           (via C→B=1, C→D=5)
Visit B:  D=6                (via B→D=3)
Visit D:  Done

Priority Queue Optimization

A naive implementation scans all nodes to find the minimum, giving O(V²) time. Using a min-heap (priority queue) reduces this to O((V + E) log V), which is much faster for sparse graphs.

Why Non-Negative Weights?

Dijkstra's algorithm assumes that once a node is visited, its shortest distance is final. Negative edge weights can violate this assumption, causing incorrect results. For graphs with negative weights, use the Bellman-Ford algorithm instead.

Reconstructing the Path

To find the actual path (not just the distance), maintain a "previous" pointer for each node. When you update a distance, also record which node caused the update. Trace back from the destination through previous pointers to reconstruct the path.

Comparison with Other Algorithms

Algorithm	Negative weights	Time complexity
Dijkstra	No	O((V+E) log V)
Bellman-Ford	Yes	O(V·E)
Floyd-Warshall	Yes	O(V³)