Separate tentative estimates from settled distances
Dijkstra’s algorithm finds shortest distances from a source when every edge weight is nonnegative. Initialize the source to zero and other vertices as unreachable. Repeatedly select the unsettled vertex with the smallest tentative distance, then examine its outgoing edges. If going through that vertex improves a neighbor’s distance, update the neighbor. This update is called relaxation. A priority queue supports choosing the smallest candidate efficiently. A predecessor recorded when a distance improves can later reconstruct a shortest path, rather than only reporting its numeric length.
Improve a concrete route step by step
Let A → B cost four, A → C cost one, C → B cost two, B → D cost one, and C → D cost seven. Processing A gives tentative distances B = 4 and C = 1. Select C next: B improves to 1 + 2 = 3, while D becomes eight. Selecting B at distance three then improves D to four. The final route to D is A → C → B → D. Discovering a route of cost eight did not make eight final; a shorter candidate emerged through a later relaxation.
| Processed vertex | B estimate | C estimate | D estimate |
|---|---|---|---|
| A | 4 | 1 | ∞ |
| C | 3 | 1 | 8 |
| B | 3 | 1 | 4 |
| D | 3 | 1 | 4 |
Explain the nonnegative-weight requirement
When the smallest tentative distance is selected, a route through a more distant unsettled vertex cannot improve it merely by adding nonnegative edges. That is the reasoning behind settling the distance. A negative edge breaks that argument because a route that currently appears longer can later become much shorter. Do not feed arbitrary negative-weight graphs to the ordinary algorithm. Zero-weight edges are allowed because zero is nonnegative. For other weight conditions, consider an appropriate method such as Bellman–Ford or a specialized algorithm for directed acyclic graphs, and state the assumptions before interpreting the result.
Name the priority-queue implementation in the bound
An adjacency-list implementation with a binary heap supporting decrease-key has a standard O((V + E) log V) time bound. A simpler implementation can instead push a new candidate whenever a distance improves and discard stale candidates when removed if their value no longer matches the recorded distance. That approach changes queue occupancy and the precise complexity accounting. Neither approach should return immediately upon merely discovering the destination. Also handle unreachable vertices explicitly and prevent numeric overflow when adding distances. Equal-distance and zero-weight cases may produce several valid shortest paths even though the minimum distance itself is well defined.
Run a heap with outdated candidates
The Python example pushes a fresh heap entry whenever a distance improves. With A→B=4, A→C=1 and C→B=2, it first stores a candidate distance four for B, then a better distance three through C. After processing three, the later entry four is rejected because it differs from B’s current best distance. Finalizing B on first discovery would incorrectly reject that improvement. This example uses comparable string vertex names. If state objects cannot be compared when priorities tie, add a monotonic tie-break counter rather than relying on object ordering.
from heapq import heappop, heappush
def shortest_paths(graph, start):
distance = {start: 0}
heap = [(0, start)]
while heap:
cost, u = heappop(heap)
if cost != distance[u]:
continue
for v, weight in graph.get(u, []):
if weight < 0:
raise ValueError('nonnegative weights required')
candidate = cost + weight
if candidate < distance.get(v, float('inf')):
distance[v] = candidate
heappush(heap, (candidate, v))
return distanceDistinguish zero weights from no path
Nonnegative weights include zero. Zero-weight edges and cycles are compatible with Dijkstra when only strictly improving distances generate updates, avoiding endless insertion of equal-distance candidates. If searching for one target, early termination belongs at its removal with a valid minimum distance, not at first discovery. Unreachable vertices must remain unreachable rather than receiving fabricated finite distances. Integer overflow and NaN can invalidate ordinary ordering comparisons, so validate the numeric domain as well as the sign of weights. Reconstructing a route additionally requires recording the predecessor on each improvement; a distance dictionary alone does not identify the chosen path.