Dijkstra's algorithm finds shortest paths from a source in a graph with non-negative edge weights. O((V+E) log V) with a binary heap — the standard tool for routing, navigation, and network protocols (OSPF, IS-IS).
Edsger Dijkstra published the algorithm in 1959. It is a greedy algorithm: at every step it commits to the unvisited node with the smallest known distance, and the non-negative-weight assumption guarantees that no later path can improve on that commitment. The same idea underlies A* search, which adds a heuristic estimate of the remaining distance to steer the greedy choice toward a goal.
Python's heapq has no decrease-key operation, so the implementation pushes a new entry whenever a distance improves and leaves the old one in the heap. Old entries are recognized later because their distance is larger than the current dist[u], and they are discarded. This "lazy deletion" keeps the code short; the heap can hold up to E entries instead of V, which changes the log factor from log V to log E, and since E is at most V squared, that is still O(log V).
The graph is the one in the code below: A to B costs 1, A to C costs 4, B to C costs 2, B to D costs 5, C to D costs 1. When B is popped, the path A-B-C (cost 3) beats the direct edge A-C (cost 4), so C is updated and pushed again; the old (4, C) entry stays in the heap and is skipped when it surfaces. The same happens for D, finally reached at cost 4 through A-B-C-D. Note that each node is finalized in increasing order of distance: A at 0, B at 1, C at 3, D at 4.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω((V+E) log V) |
Θ((V+E) log V) |
O((V+E) log V) |
O(V) |
Maintain dist[v] initialized to ∞ except dist[source] = 0, and a min-heap keyed by tentative distance. Repeatedly pop the closest unvisited node; relax each outgoing edge (v, w) — if dist[v] + weight < dist[w], update and push w. Once a node is popped, its distance is final (relies on edges being non-negative).
import heapq
def dijkstra(graph, source):
"""graph[u] = list of (v, weight). Returns dict of shortest distances."""
dist = {n: float("inf") for n in graph}
dist[source] = 0
pq = [(0, source)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # stale entry
for v, w in graph[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist
graph = {
"A": [("B", 1), ("C", 4)],
"B": [("C", 2), ("D", 5)],
"C": [("D", 1)],
"D": [],
}
print(dijkstra(graph, "A")) # {'A': 0, 'B': 1, 'C': 3, 'D': 4}Distances alone rarely suffice for routing; you need the route. Record the predecessor whenever an edge improves a distance, then walk predecessors back from the target. Stopping as soon as the target is popped is a valid optimization for single-pair queries, because its distance is final at that moment.
import heapq
def shortest_path(graph, source, target):
dist = {source: 0}
prev = {}
pq = [(0, source)]
while pq:
d, u = heapq.heappop(pq)
if u == target:
break # target is final; stop early
if d > dist.get(u, float("inf")):
continue
for v, w in graph[u]:
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v], prev[v] = nd, u
heapq.heappush(pq, (nd, v))
if target not in dist:
return None, []
path, node = [], target
while node != source:
path.append(node)
node = prev[node]
path.append(source)
return dist[target], path[::-1]
graph = {"A": [("B", 1), ("C", 4)], "B": [("C", 2), ("D", 5)], "C": [("D", 1)], "D": []}
print(shortest_path(graph, "A", "D")) # (4, ['A', 'B', 'C', 'D'])When to use it. Dijkstra is the default for single-source shortest paths on weighted graphs with non-negative weights: road networks, network routing (OSPF and IS-IS compute shortest-path trees this way), game maps, and dependency costs. For unweighted graphs, plain BFS gives the same answer in O(V + E). For a single target with a good distance estimate, A* explores far fewer nodes. With negative edges, use Bellman-Ford, or Johnson's algorithm for all pairs.
if d > dist[u]: continue the result is still correct but nodes are re-expanded, which can blow up running time.graph, dist initialized from the keys raises KeyError; use dist.get as in the path version.