Dijkstra's Algorithm

Shortest paths from one vertex in a graph with non-negative weights, by repeatedly settling the closest unsettled vertex.

Level: advanced

What is it?

Dijkstra's algorithm computes the shortest distance from a source to every other vertex when all edge weights are non-negative. It keeps a tentative distance for each vertex and a priority queue ordered by distance. It repeatedly takes the closest unsettled vertex, whose distance is now final, and relaxes its outgoing edges: if going through it improves a neighbor's distance, update it.

Why does it matter?

Weighted shortest paths power maps, network routing, and scheduling. OSPF routers run Dijkstra's algorithm over the link-state database to build their forwarding tables, so it is where graph algorithms meet the networking section.

Mental model

Pouring water into a network of pipes from one point, where pipe length is travel time. The water reaches the nearest junction first, then the next nearest. The moment water arrives at a junction, that time is the shortest possible, because anything faster would already have arrived.

How it works

Greedy: always settle the unsettled vertex with the smallest known distance.
Relaxation: if dist[u] + w(u, v) < dist[v], update dist[v] and push it into the queue.
Correct only with non-negative weights: a negative edge can make a settled vertex improvable later.
With a binary heap, time is O((V + E) log V). Skip stale queue entries whose distance is already outdated.
Store predecessors to reconstruct the actual path, not just its length.
For negative weights use Bellman–Ford; for unweighted graphs plain BFS is enough.

Steps

Set the source distance to 0
Push it into a min-heap
Pop the closest vertex
Relax each outgoing edge
Repeat until the heap is empty

Code example: Shortest distances with a heap

import heapq

def dijkstra(graph, src):
    dist = {src: 0}
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")):
            continue                        # stale queue entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

g = {"A": [("B", 4), ("C", 1)], "C": [("B", 2)], "B": []}
print(dijkstra(g, "A"))   # {'A': 0, 'B': 3, 'C': 1}

Complexity and trade-offs

Time: O((V + E) log V) with a binary heap

Space: O(V + E)

Trade-offs

Efficient for non-negative weights from a single source
Fails with negative edges
Computes distances to all vertices, even if you only need one

Real-world usage

OSPF and IS-IS link-state routing
Maps and navigation
Latency-based service routing and game AI pathfinding (often with A*)

Common mistakes

Using it on a graph with negative edge weights.
Forgetting to skip stale heap entries, so work is repeated.
Using a plain list as the frontier and getting O(V²) time without meaning to.

Interview questions

Why does Dijkstra's algorithm fail with negative edges?

It assumes that once a vertex is settled its distance is final, because any other route would be at least as long. A later negative edge could make a shorter route to a settled vertex, which the algorithm never revisits.

What is the complexity with a binary heap?

O((V + E) log V): each edge may cause a heap push, each push or pop costs O(log V), and there are at most E pushes.

How is Dijkstra used in networking?

Link-state protocols such as OSPF flood the topology to every router, and each router runs Dijkstra on its own copy to compute the shortest-path tree and the next hop for every destination.