Algorithms and data structures · Intermediate

Dijkstra’s algorithm: settle shortest paths with nonnegative weights

Choose the smallest tentative distance and relax edges while respecting the nonnegative-weight precondition.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Separate tentative estimates from settled distances
  2. Improve a concrete route step by step
  3. Explain the nonnegative-weight requirement
  4. Name the priority-queue implementation in the bound
  5. Run a heap with outdated candidates
  6. Distinguish zero weights from no path
  7. Ask Logeia about this articleCheck your understanding

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 vertexB estimateC estimateD estimate
A41∞
C318
B314
D314

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.

Python
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 distance

Distinguish 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.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 11

Choose a learning path