Data Structures & Algorithms / Ordered structures and graph reasoning / Lesson 11

Weighted shortest paths and relaxation

Choose an algorithm from weight assumptions and preserve current-distance authority when priority entries become obsolete.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

A distance is a path claim with assumptions
Dijkstra relies on nonnegative extension costs
Bellman-Ford relaxes under a different proof

A distance is a path claim with assumptions

A shortest-path problem minimizes total edge weight, not necessarily the number of edges. BFS applies directly when all edge costs are equal; arbitrary nonnegative costs require another argument. Define directedness, represented vertices, source, numeric domain, and unreachable output. The examples use finite integer weights and retain infinity only for unreachable vertices. Negative cycles reachable from the source can make some finite shortest distances undefined because repeated traversal keeps reducing cost. An algorithm must detect or otherwise handle that situation rather than returning a plausible finite value after an arbitrary number of iterations.

Dijkstra relies on nonnegative extension costs

Dijkstra repeatedly takes the smallest currently known tentative distance. With nonnegative edges, no path that goes through a later, no-smaller frontier can improve a correctly settled distance. The first program checks the weight precondition and inserts a new heap entry after improvement. Older entries remain in the heap, so it skips a popped entry unless its stored distance equals the authoritative distance map. This lazy strategy avoids a custom decrease-key operation. Its heap may contain O(E) entries, yielding O((V+E) log(V+E)) as a convenient bound for this implementation, not an assumed V-sized indexed heap.

python Self-contained Python3 algorithm example using synthetic local data.

import heapq
from math import inf

def dijkstra(graph, source):
    if source not in graph:
        raise ValueError("Unknown source")
    if any(weight < 0 for edges in graph.values() for _, weight in edges):
        raise ValueError("Dijkstra requires nonnegative weights")
    distance = {vertex: inf for vertex in graph}
    distance[source] = 0
    heap = [(0, source)]
    while heap:
        cost, vertex = heapq.heappop(heap)
        if cost != distance[vertex]:
            continue
        for neighbor, weight in graph[vertex]:
            candidate = cost + weight
            if candidate < distance[neighbor]:
                distance[neighbor] = candidate
                heapq.heappush(heap, (candidate, neighbor))
    return distance

graph = {"A": [("B", 9), ("C", 2)], "B": [], "C": [("B", 3)], "D": []}
print(sorted(dijkstra(graph, "A").items()))

Expected output

[('A', 0), ('B', 5), ('C', 2), ('D', inf)]

B first receives9 and later5 through C. The obsolete9 entry is skipped; D remains unreachable.

Bellman-Ford relaxes under a different proof

Bellman-Ford repeatedly considers all edges. After enough rounds, every shortest simple path with at most V-1 edges has had the opportunity to propagate; a further reachable improvement signals a reachable negative cycle. The second program uses in-place relaxations, which may propagate several edges in one round, so its invariant is an at-least coverage guarantee rather than exactly one more edge per round. It rejects a reachable negative cycle and leaves unreachable components irrelevant to source distances. The usual bound is O(VE) work, with O(V) distance storage excluding the input edge list.

python Self-contained Python3 algorithm example using synthetic local data.

from math import inf

def bellman_ford(vertices, edges, source):
    distance = {vertex: inf for vertex in vertices}
    if source not in distance:
        raise ValueError("Unknown source")
    distance[source] = 0
    for _ in range(len(vertices) - 1):
        changed = False
        for start, end, weight in edges:
            if distance[start] != inf and distance[start] + weight < distance[end]:
                distance[end] = distance[start] + weight
                changed = True
        if not changed:
            break
    for start, end, weight in edges:
        if distance[start] != inf and distance[start] + weight < distance[end]:
            raise ValueError("Reachable negative cycle")
    return distance

print(sorted(bellman_ford(["A", "B", "C"],
    [("A", "B", 4), ("A", "C", 5), ("B", "C", -2)], "A").items()))

Expected output

[('A', 0), ('B', 4), ('C', 2)]

The negative edge is valid here because the graph has no reachable negative cycle. It would violate Dijkstra’s declared precondition.

Keep path reconstruction and unreachable state explicit

A predecessor map can record the edge that last improved each distance. Reconstruct only when the destination is reachable, and stop at the source under a proven predecessor policy. Do not follow arbitrary predecessors forever after a negative-cycle failure. Several shortest paths can tie; the code’s strict-improvement rule and adjacency order choose one if reconstruction is added. Distance equality alone does not define a unique path. For floating-point weights, NaN, infinities, and rounding require a different accepted numeric contract; this course’s exact integer fixtures avoid pretending those issues disappear automatically.

Validate graph shape before interpreting failures

Both programs assume every edge endpoint belongs to the represented vertex set. A public parser should validate this separately, along with weight type and finite-domain requirements. A KeyError from an unknown neighbor is a malformed-graph symptom, not evidence that shortest-path theory failed. Heap tuples here use comparable string vertices to break equal-distance ties; opaque vertex objects need a unique counter before the payload. Do not mutate adjacency lists while traversing them. The current distance map is authoritative for one immutable graph snapshot, and a changed graph may invalidate all prior distances.

Cross-check algorithms where their assumptions overlap

For tiny nonnegative graphs, compare Dijkstra and Bellman-Ford with an independent all-pairs reference such as Floyd-Warshall. Include a cheaper indirect path, zero-weight edges, equal alternatives, disconnected vertices, and stale heap entries. Test negative-edge rejection separately from Bellman-Ford’s reachable-cycle detection, including an unreachable negative cycle that should not poison source distances. A finite test suite complements relaxation proofs. All checks use synthetic in-memory graphs and no graph service, database, network operation, or load test. Record the exact implementation bounds rather than claiming a different heap or weight model.

Common errors and fixes

A negative edge is accepted by a Dijkstra contract

Why it happens: The weight assumption behind settlement was omitted.
How to fix it: Reject negative weights or select an appropriate algorithm.
Prevent it next time: Test a negative-edge fixture explicitly.

Old heap entries cause repeated obsolete processing

Why it happens: Popped priority was not compared with current distance.
How to fix it: Skip entries that disagree with the authoritative map.
Prevent it next time: Include a vertex improved after an earlier enqueue.

Unreachable negative cycles reject a valid source query

Why it happens: Cycle detection ignored source reachability.
How to fix it: Require finite source distance before testing further improvement.
Prevent it next time: Test disconnected negative-cycle components.

Check your understanding

1. Why does B become5 rather than9 in the first graph?

Show worked solution

The direct edge A to B costs9, while A to C to B costs2+3=5. Relaxation improves the authoritative distance and inserts a new5 priority. When9 is later popped, it is obsolete and must not replace or reprocess the current result.

2. Why is a reachable negative cycle different from one in a disconnected component?