Dijkstra's algorithm finds the shortest path in a weighted graph from a single source vertex to every other vertex. It solves shortest-path problems when edge weights are non-negative, and it is used in applications ranging from network routing to map navigation.

BFS only solves the shortest-path problem on unweighted graphs, where every edge counts the same. Once edges have distinct weights, a path with fewer edges is not necessarily shorter than a path with more edges, and BFS gives the wrong answer.

Dijkstra's algorithm handles weighted graphs by always extending the lowest-cost known path next, using a greedy strategy backed by a priority queue.

Dijkstra's algorithm, invented by Edsger Dijkstra in 1956, is a greedy single-source shortest path algorithm for graphs with non-negative edge weights. Given a source vertex, it finds the shortest path from that source to every other vertex in the graph.

Breaking that down:

Here is a weighted graph we will use throughout this chapter:

Running Dijkstra's from vertex A finds the shortest distance from A to every other vertex. The algorithm arrives at A->C->B->D->E with a total cost of 7, and the following sections walk through exactly how.

The algorithm relies on two key ideas: a priority queue (min-heap) and edge relaxation.

Priority Queue

Instead of processing vertices in arbitrary order, Dijkstra's uses a min-heap to always process the vertex with the smallest tentative distance next. This is what makes it greedy: it always commits to the closest unvisited vertex.

The min-heap replaces a linear scan over all vertices to find the one with the smallest tentative distance. Each extract-min runs in O(log V) instead of O(V).

Edge Relaxation

When the algorithm visits a vertex u and looks at its neighbor v, it checks whether the path through u is shorter than the best path found to v so far. If yes, v's distance is updated. This process is called relaxation.

The name comes from the idea of "relaxing" the constraint on how short the path to v can be, bringing it closer to the true shortest distance.

The Algorithm

Here is a diagram showing the progression on our earlier graph, starting from A:

Green nodes are finalized (visited). Orange nodes have updated distances but have not been finalized yet. The algorithm always picks the orange node with the smallest distance next.

The correctness of Dijkstra's algorithm rests on one key insight: once a vertex is extracted from the priority queue, its distance is finalized, and no shorter path to it can ever be found.

Why is this true? Consider the moment vertex u is extracted from the min-heap with distance d. Could there be some other, undiscovered path to u with a shorter distance? That path would have to go through at least one unvisited vertex w. But w is still in the heap, and its distance is greater than or equal to d (because u was extracted first, meaning u had the smallest distance).

Since all edge weights are non-negative, any path through w to u would have a total distance of at least dist[w], which is already >= d. There is no shorter path.

This is the greedy choice: u's distance can be committed because no future discovery can improve it.

Why Non-Negative Weights Are Required

The argument above falls apart if edges can have negative weights. If there is a negative-weight edge from w to u, then a path through w could be shorter than d, even though dist[w] > d. The greedy assumption, that extracting the smallest distance from the heap gives a finalized answer, no longer holds.

The "Why Dijkstra Fails with Negative Weights" section works through a concrete example of this failure. Dijkstra's algorithm requires all edge weights to be non-negative. For graphs with negative weights, use the Bellman-Ford algorithm instead.

The implementation uses an adjacency list and a min-heap (priority queue):

Tracing Dijkstra's on a slightly larger graph helps solidify the concept. Consider this graph with 6 vertices (0 through 5):

Source vertex: 0

Initial state: dist = [0, INF, INF, INF, INF, INF], PQ = [(0, 0)]

Consider this graph:

Running Dijkstra from A:

Dijkstra reports dist[B] = 1, but the true shortest path is A->C->B with cost 3 + (-5) = -2. The algorithm fails because it finalized B too early. The greedy assumption, that the smallest distance in the heap is the true shortest, breaks down when negative edges exist.

Dijkstra with Path Reconstruction

Many problems require the actual path, not just the shortest distance. To reconstruct the path, maintain a parent[] array that records which vertex each vertex was relaxed from.

The only addition to the standard algorithm is the parent[] array and the backtracking loop at the end. Path reconstruction is a common follow-up.

Bidirectional Dijkstra

For point-to-point shortest path queries (source to a specific target), Dijkstra can run from both the source and the target simultaneously, stopping when the two searches meet. This often reduces the number of vertices explored, though the worst-case complexity stays the same.

Bidirectional Dijkstra is used in road-network and large-graph applications. Map services typically layer additional preprocessing techniques like Contraction Hierarchies on top of the basic algorithm.

0-1 BFS

When all edge weights are either 0 or 1, a deque (double-ended queue) can replace the priority queue. Add 0-weight edges to the front of the deque and 1-weight edges to the back. This gives O(V + E) time instead of O((V + E) log V), since the heap overhead is removed.

Time Complexity

The time complexity depends on the priority queue implementation:

Breaking down O((V + E) log V) for the binary heap approach:

For dense graphs (E is close to V^2), the array-based approach with O(V^2) can be faster because it avoids heap overhead. For sparse graphs (E is much less than V^2), the binary heap approach wins.

Space Complexity