Dijkstra’s algorithm answers “what’s the cheapest way to reach every node from one source?” in a weighted graph — the engine behind GPS routing, OSPF network routing, and package delivery.

It works by greedily expanding the closest unvisited node, using a min-priority queue to always pick the next-best frontier node. Its one hard requirement: no negative edge weights.

How It Works

1. Initialize: set dist[source] = 0, all others ∞. Insert the source into the priority queue.
2. Extract min: remove the node with the smallest known distance from the priority queue.
3. Relax edges: for each neighbor, check if routing through the current node gives a shorter path. If so, update its distance and parent.
4. Repeat: until the priority queue is empty. Every extracted distance is now final.

Key Insight

The greedy step is valid precisely because edge weights are non-negative: once a node is extracted from the queue with its minimum distance, no future (longer) path could possibly improve it. This is the shortest-path analogue of the cut property.

The relax operation — “if dist[u] + w < dist[v], update dist[v]” — is the entire engine. Everything else just decides the order of relaxations: always the most promising first.

Worked Example

Run Dijkstra on the visualizer’s weighted graph, source S:

Shortest distances: S=0, A=2, B=4, C=5, D=5, E=7, T=8. Notice B→D improves D from 9 to 5 after A was already processed — Dijkstra re-relaxes neighbors and the priority queue fixes the ordering. Watch the distance table in the visualizer update as each node is finalized.

Edge Cases & Pitfalls

• Negative edges — Dijkstra silently returns wrong answers: the greedy extraction is invalid. Use Bellman-Ford.
• Disconnected nodes — unreachable nodes keep dist = ∞: report them as such.
• Multiple shortest paths — any is valid; parent pointers reconstruct one of them.
• Dense graphs — a simple array-based “queue” gives O(V²), which beats a heap when E ≈ V². The heap version O((V+E) log V) is better for sparse graphs.

Comparison With Other Path Algorithms

Applications

• GPS navigation — shortest road between two points
• Network routing — OSPF protocol
• Map services — travel times and distances
• Logistics — optimizing delivery routes
• Social networks — shortest connection chains

Practice Trajectory

1. Hand-trace Dijkstra on the visualizer graph starting at A, recording the distance table each round.
2. Explain why extracting a node from the min-heap finalizes its distance given non-negative weights.
3. Construct a small graph with a negative edge and show where Dijkstra fails.
4. Reconstruct the shortest path from S to T using parent pointers.
5. Compare Dijkstra’s behavior on sparse vs dense graphs and when to prefer O(V²).