Dijkstra Algorithm

Definition: A greedy single-source shortest path algorithm that finds the minimum-cost path from a source node to every other node in a graph with non-negative edge weights.

How It Works

Dijkstra maintains a priority queue (min-heap) of tentative distances, initialized to 0 for the source and infinity for every other node:

dist[source] = 0, dist[all others] = infinity
pq = {(0, source)}
while pq is not empty:
    d, u = pq.extract_min()
    if u already finalized: continue
    mark u finalized
    for (v, weight) in u.edges:
        if dist[u] + weight < dist[v]:
            dist[v] = dist[u] + weight
            pq.insert((dist[v], v))

The core operation is relaxation: for every outgoing edge (u, v) with weight w, check whether routing through u improves the best known distance to v, and update it if so. The algorithm repeatedly extracts the unvisited node with the smallest tentative distance and finalizes it.

Correctness depends entirely on the greedy choice property: once a node is popped with its minimum distance, no future relaxation can ever improve it, because any other path to that node would have to go through a node with a larger or equal tentative distance, and edge weights are non-negative so that path can’t possibly be shorter. This is exactly why negative edge weights break the algorithm: a big negative edge encountered later could retroactively beat an already-finalized “shortest” path.

The algorithm can terminate early once the target node itself is popped from the priority queue, avoiding computing distances to the entire graph when only one destination is actually needed.

Complexity Analysis

Implementation	Time Complexity
Binary heap priority queue	O((V + E) log V)
Naive array (no heap)	O(V^2), faster in practice on dense graphs
Fibonacci heap	O(E + V log V)

V is vertices, E is edges. The binary-heap version is the standard practical choice; the array version can beat it on dense graphs (E close to V^2) because it avoids heap overhead entirely.

Why It Matters

• Core algorithm for network routing protocols; OSPF uses Dijkstra internally to compute shortest paths across link-state advertisements between routers.
• Serves as the direct ancestor of A* search, which adds a heuristic function to prioritize nodes likely to be near the goal, dramatically pruning the search space in practice while preserving optimality guarantees when the heuristic is admissible.
• Demonstrates the greedy-algorithm-with-priority-queue pattern reused across many other shortest-path and minimum-spanning-tree problems; Prim’s MST algorithm shares nearly identical structure, just relaxing “distance to the tree” instead of “distance from the source.”

Common Pitfalls

• Fails or produces incorrect results on graphs containing negative edge weights, since the greedy finalize-on-pop assumption breaks down; Bellman-Ford (O(V*E)) must be used instead whenever negative weights are possible.
• Re-inserting a node into the priority queue on every relaxation, instead of decreasing its existing key, can bloat the heap with stale entries; most practical implementations simply allow duplicate entries and skip already-finalized nodes on pop, rather than implementing a true decrease-key operation.
• Using Dijkstra when all edge weights are equal is wasted overhead; plain Breadth-First Search (BFS) solves that exact case in O(V + E) without needing a heap at all.
• Forgetting that Dijkstra computes shortest paths from a single source, not all pairs; for all-pairs shortest paths, Floyd-Warshall (O(V^3)) or running Dijkstra from every node individually is required instead.
• Assuming Dijkstra explores nodes in the same order as BFS; it explores by cumulative weight, not by hop count, so a low-hop-count path can be processed much later than a high-hop-count but lower-weight one.

Comparison

	Dijkstra	Bellman-Ford	A*	BFS
Handles negative weights	No	Yes (detects negative cycles too)	No (typically)	N/A (unweighted)
Time complexity	O((V+E) log V)	O(V * E)	Depends on heuristic quality	O(V + E)
Guarantees optimal path	Yes, non-negative weights	Yes	Yes, with an admissible heuristic	Yes, unweighted only
Uses a heuristic	No	No	Yes	No

Example

GPS navigation computing the fastest driving route, weighing road segments by distance or estimated travel time, is a direct real-world application. On a graph with edges A-B(4), A-C(1), C-B(2), B-D(5), C-D(8), Dijkstra from A pops C first (distance 1), relaxes B to 1+2=3 (better than the direct A-B edge of 4), then pops B (distance 3), then relaxes D to 3+5=8. The result, A -> C -> B -> D at total cost 8, beats the naive-looking direct route A -> C -> D at cost 9, exactly the kind of non-obvious shortcut Dijkstra is designed to find.

Priority Queue State, Step by Step

Tracing the exact dist[] array and priority queue contents for the same graph (A-B(4), A-C(1), C-B(2), B-D(5), C-D(8)), starting from A:

init:     dist={A:0, B:inf, C:inf, D:inf}    pq=[(0,A)]

pop (0,A): finalize A
  relax A-B(4): dist[B]=4, pq.insert(4,B)
  relax A-C(1): dist[C]=1, pq.insert(1,C)
  pq=[(1,C), (4,B)]

pop (1,C): finalize C
  relax C-B(2): 1+2=3 < 4, dist[B]=3, pq.insert(3,B)
  relax C-D(8): 1+8=9 < inf, dist[D]=9, pq.insert(9,D)
  pq=[(3,B), (4,B), (9,D)]     # stale (4,B) entry still in the queue

pop (3,B): finalize B
  relax B-D(5): 3+5=8 < 9, dist[D]=8, pq.insert(8,D)
  pq=[(4,B), (8,D), (9,D)]

pop (4,B): B already finalized -> skip (stale entry)
  pq=[(8,D), (9,D)]

pop (8,D): finalize D
  no outgoing edges to relax
  pq=[(9,D)]

pop (9,D): D already finalized -> skip (stale entry)
  pq=[] -> done

Final distances: A=0, C=1, B=3, D=8. The stale (4,B) and (9,D) entries are the standard lazy-deletion approach mentioned above: cheaper to leave outdated entries in the heap and skip them on pop than to implement a true decrease-key.

Reconstructing the Path

Dijkstra as described only computes distances. To recover the actual path, store a prev[node] pointer every time a relaxation improves dist[v], recording which node v was reached from. After the algorithm finishes, walk prev pointers backward from the target to the source, then reverse the resulting list to read it start to finish.

Why Non-Negative Weights Are Required

The greedy correctness argument relies on the fact that once a node is popped with the smallest tentative distance in the queue, every other candidate path to it must route through a node with an equal or larger tentative distance, and since all edge weights are non-negative, adding more edges can only add more cost, never less. A negative edge breaks this: a path that currently looks longer could become shorter after crossing a negative edge later, but by then the node may have already been incorrectly finalized. Bellman-Ford handles this by relaxing every edge V-1 times instead of greedily finalizing nodes, trading speed for correctness under negative weights.

Variants

• A* Search: Dijkstra plus a heuristic function h(v) estimating remaining distance to the goal, prioritizing dist[v] + h(v) instead of just dist[v]. With an admissible heuristic (never overestimates true remaining distance), A* still finds the optimal path while typically exploring far fewer nodes.
• Bidirectional Dijkstra: runs the search simultaneously from the source and the target, stopping when the two search frontiers meet, which can roughly halve the effective search radius in practice.
• Johnson’s Algorithm: reweights all edges to be non-negative using a Bellman-Ford pre-pass, then runs Dijkstra from every node, giving an efficient all-pairs shortest path solution for sparse graphs that may contain negative (but not negative-cycle) edges.

Real-World Systems

• OSPF (Open Shortest Path First), a widely used interior gateway routing protocol, runs Dijkstra’s algorithm on each router’s local view of the network topology to compute forwarding tables.
• Mapping and navigation services (the general class of tools behind turn-by-turn directions) use Dijkstra or, more commonly in practice, A* and contraction-hierarchy variants built on the same relaxation principle, to compute fastest or shortest routes.
• Video game pathfinding for NPCs on a fixed-cost grid or navmesh commonly uses A*, Dijkstra’s heuristic-guided descendant, precisely because game maps are static enough to precompute good heuristics.

Common Interview Questions

• Why does Dijkstra fail with negative edge weights, but BFS never has that concern? — BFS never uses edge weights at all, only hop count, so there’s nothing for a negative value to corrupt. Dijkstra’s correctness specifically depends on non-negative weights to justify finalizing nodes greedily.
• How would you adapt Dijkstra to find the shortest path to a specific target rather than all nodes? — stop as soon as the target is popped from the priority queue, since its distance is finalized at that point; no need to keep processing the rest of the graph.
• What data structure change turns Dijkstra into Prim’s MST algorithm? — relax by “distance to the nearest tree node” instead of “distance from the source,” and track visited/tree membership instead of shortest-path distance; the priority-queue-driven loop structure stays nearly identical.

Related Terms

• Priority Queue and Heap
• Breadth-First Search (BFS)
• Graph Representation
• Big-O Notation
• BGP and Autonomous Systems