8.3 Weighted Shortest Paths: Fewer Edges Can Cost More

Chapter 8 · Weighted Shortest Path | Prerequisites: BFS and DFS, Heap, and Topological Sort. This page compares Dijkstra, Bellman–Ford, and DAG topological relaxation using a unified interface and retains predecessors to reconstruct paths.

Compare Sums of Edge Weights

Once edges carry travel times, counting edges is not enough. Consider two routes from A to E:

A → B → E        6 + 2 = 8
A → C → D → E    3 + 1 + 1 = 5

The second route passes through one more intermediate node but takes less time. Here, we are minimizing the sum of edge weights, not the number of edges.

1. All edge weights are non-negative: Dijkstra.
2. Negative weights are possible: Bellman–Ford.
3. Known to be a DAG: relax in topological order, can include negative weights.

Negative weight isn't "negative physical distance", it can represent rebates, energy recovery, or currency gains. A negative-weight cycle reachable from the start reduces cost on each circuit. Vertices on or reachable from that cycle have no finite lower distance bound; other vertices need not be affected. This page's Bellman–Ford raises an exception on such a cycle instead of returning partial results.

A unified, executable implementation

Vertices may be hashable objects, including None, with reflexive, stable equality and stable hashes. Dijkstra heap entries carry a unique increasing sequence number, so equal distances never require comparing vertex objects. All three algorithms return distance and parent. Distances include every input vertex, using inf for unreachable vertices. Parents include only reachable vertices, with the start pointing to itself. reconstruct_path returns None for an unknown or unreachable target.

The example accepts integer weights and rejects floats, NaN, and infinities before comparison. Python integer addition cannot overflow, so relaxation and negative-cycle checks remain exact; fractional costs can be converted to integer units. A floating-point version needs separate decisions about rounding, overflow, and negative-cycle detection errors.

Dijkstra and DAG relaxation take {vertex: [(neighbor, weight), ...]} and add vertices that appear only as endpoints. Bellman–Ford takes an explicit vertex list and (source, target, weight) edge list, rejecting missing endpoints. Parallel edges are allowed; undirected edges require both directions. Each algorithm copies input containers and consumes input iterators.

from collections import deque
from itertools import count
import heapq
import math

def _require_weight(weight):
    if not isinstance(weight, int):
        raise TypeError("edge weight must be an integer")

def _weighted_adjacency(graph):
    adjacency = {node: list(edges) for node, edges in graph.items()}
    for edges in list(adjacency.values()):
        for neighbor, weight in edges:
            _require_weight(weight)
            adjacency.setdefault(neighbor, [])
    return adjacency

def reconstruct_path(parent, start, target):
    if start not in parent or target not in parent:
        return None
    path = []
    current = target
    seen = set()
    while current in parent:
        if current in seen:
            raise ValueError("parent map contains a cycle")
        seen.add(current)
        path.append(current)
        if current == start:
            path.reverse()
            return path
        current = parent[current]
    return None

def dijkstra(graph, start):
    """Single-source shortest path when all edge weights are non-negative."""
    adjacency = _weighted_adjacency(graph)
    if start not in adjacency:
        raise KeyError(f"unknown start vertex: {start!r}")
    for edges in adjacency.values():
        for _, weight in edges:
            if weight < 0:
                raise ValueError("Dijkstra requires non-negative edge weights")

    distance = {node: math.inf for node in adjacency}
    parent = {start: start}
    distance[start] = 0
    sequence = count()
    heap = [(0, next(sequence), start)]

    while heap:
        known_distance, _, node = heapq.heappop(heap)
        if known_distance != distance[node]:
            continue
        for neighbor, weight in adjacency[node]:
            candidate = known_distance + weight
            if candidate < distance[neighbor]:
                distance[neighbor] = candidate
                parent[neighbor] = node
                heapq.heappush(heap, (candidate, next(sequence), neighbor))
    return distance, parent

def bellman_ford(nodes, edges, start):
    """Detect negative cycles reachable from start, and only those cycles."""
    nodes = list(dict.fromkeys(nodes))
    node_set = set(nodes)
    if start not in node_set:
        raise KeyError(f"unknown start vertex: {start!r}")
    edges = list(edges)
    for source, target, weight in edges:
        _require_weight(weight)
        if source not in node_set or target not in node_set:
            raise KeyError("edge endpoint is missing from nodes")

    distance = {node: math.inf for node in nodes}
    parent = {start: start}
    distance[start] = 0

    for _ in range(max(0, len(nodes) - 1)):
        changed = False
        for source, target, weight in edges:
            if distance[source] == math.inf:
                continue
            candidate = distance[source] + weight
            if candidate < distance[target]:
                distance[target] = candidate
                parent[target] = source
                changed = True
        if not changed:
            break

    for source, target, weight in edges:
        if distance[source] != math.inf:
            if distance[source] + weight < distance[target]:
                raise ValueError("reachable negative-weight cycle")
    return distance, parent

def dag_shortest_paths(graph, start):
    """Single-source DAG shortest paths; reject any directed cycle."""
    adjacency = _weighted_adjacency(graph)
    if start not in adjacency:
        raise KeyError(f"unknown start vertex: {start!r}")

    indegree = {node: 0 for node in adjacency}
    for edges in adjacency.values():
        for neighbor, _ in edges:
            indegree[neighbor] += 1
    queue = deque(node for node in adjacency if indegree[node] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor, _ in adjacency[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    if len(order) != len(adjacency):
        raise ValueError("DAG shortest paths requires an acyclic graph")

    distance = {node: math.inf for node in adjacency}
    parent = {start: start}
    distance[start] = 0
    for node in order:
        if distance[node] == math.inf:
            continue
        for neighbor, weight in adjacency[node]:
            candidate = distance[node] + weight
            if candidate < distance[neighbor]:
                distance[neighbor] = candidate
                parent[neighbor] = node
    return distance, parent

if __name__ == "__main__":
    roads = {
        "A": [("B", 6), ("C", 3)],
        "B": [("E", 2)],
        "C": [("D", 1)],
        "D": [("E", 1), ("B", 1)],
        "E": [],
        "Z": [],
    }
    distance, parent = dijkstra(roads, "A")
    print(distance)
    print(reconstruct_path(parent, "A", "E"))

Expected core output is:

{'A': 0, 'B': 5, 'C': 3, 'D': 4, 'E': 5, 'Z': inf}
['A', 'C', 'D', 'E']

Dijkstra: Why Greedy Works

Starting from A, we first know that B's tentative distance is 6 and C's is 3. The priority queue picks C first, then C updates D's distance to 4; D subsequently updates both B's and E's distances to 5.

Determine A=0 → B=6, C=3
Determine C=3 -> D=4
Determine D=4 -> B=5, E=5
Determine E=5
Determine B=5 -> E remains 5

When edge weights are all non-negative, undecided paths can only keep or increase cost, so the top candidate in the heap can be finalized. The code doesn't permanently close nodes using visited, instead it skips heap entries whose distances have expired, this is a common priority queue implementation.

Negative weights would break this proof. To ensure early and consistent failure, this implementation first scans the entire input graph; even if negative edges are in an unreachable region from the start, Dijkstra is rejected. Python heapq provides a min-heap interface, see Python heapq.

This implementation retains stale heap entries. Each edge can relax successfully at most once, but a vertex may have several heap entries. The heap can hold O(E+1) entries, not just O(V). Including input copying and validation, time is O(V + E log(E+2)) and additional space is O(V+E), including the adjacency copy, distance/parent maps, and heap. For a simple graph without parallel edges, E <= V² allows the familiar O((V+E) log(V+1)) bound. These counts assume average constant-time hash access; integer arithmetic and comparison also depend on bit length.

Bellman-Ford: Repeated Relaxation

For edge u → v (w), if distance[u] + w < distance[v], then update v. A simple shortest path without cycles has at most V-1 edges, so at most V-1 rounds are needed; the process can be terminated early if no updates occur in a round.

Scan once more; if still updatable and u is reachable from the start, then a reachable negative-weight cycle exists. Note the detection scope:

• This function does not report negative cycles that are disconnected from the source.
• If the requirement is "does the entire graph contain a negative-weight cycle," add a super source node with weight 0 connected to all vertices, then run the detection.

The official documentation also distinguishes between negative cycles reachable from a single source and negative cycles in components not containing the source: NetworkX Bellman–Ford.

Each round scans at most E edges, with at most V-1 rounds plus a final check. Including initialization of V vertices gives O(V(E+1)) time, usually shortened to O(VE) when E>0. The edge-list copy, sets, and result maps use O(V+E) space. Support for negative edges alone does not make it the default replacement for Dijkstra.

DAG: Relax once in dependency order

DAG has a topological order. All edges entering u are processed before processing u, each edge is relaxed only once, so the time complexity is O(V + E), and negative weights are allowed. Including the adjacency copy, additional space is O(V+E). The code verifies that the topological sort covers every vertex. A directed cycle anywhere is rejected, even in an unreachable region.

Course Dependencies Are Not Always a Shortest-Path Problem

A course dependency graph is good for explaining topological order but not necessarily for explaining "when the earliest semester each course can be taken."

• Shortest Path selects the dependency chain with the smallest total weight.
• Typically, the completion time is determined by the longest prerequisite chain or a more comprehensive scheduling model when all prerequisites must be fulfilled.

Therefore, if a course depends on both "machine learning" and "Python," the shortest path in the DAG only shows the cheapest route from a starting point, it doesn't automatically prove when all prerequisites are satisfied. This distinction matters more than remembering a line of code.

Quick Reference for Three Algorithms

Algorithm	Edge Weight Condition	Negative Cycle	Time
BFS	Unweighted or equal nonnegative weights	Not applicable	O(V + E)
This Dijkstra with a lazy binary heap	Nonnegative	Does not handle negative weights	O(V + E log(E+2))
Bellman–Ford	Can handle negative weights	Detects negative cycles reachable from source	O(V(E+1))
Topological Sort with Relaxation	Can have negative weights, must be acyclic	Reject if input has cycles	O(V + E)

A more complete algorithm entry and complexity comparison can be found at NetworkX shortest paths.

Troubleshooting Checklist

• Did Dijkstra verify that all edge weights are non-negative before?
• When vertices in a heap have equal distances, are the vertex objects compared?
• Are neighbors still included in the result mapping when they appear only at the endpoints of edges?
• Does Bellman–Ford only relax edges from a finite distance u?
• Is a negative cycle detected globally across the entire graph, or only in the source-reachable / reachable from source portion of the graph?
• Does the DAG algorithm actually verify that there's no cycle?
• Does the output contain only distance, or is the predecessor path also retained?
• Fails to reach target returns None or an empty list? The API must be fixed.

Get Out of the Weighted Network

The choice of shortest path algorithm depends on the input constraints: non-negative edge weights allow Dijkstra's greedy approach; general graphs with negative weights can use Bellman–Ford, with a clear policy for source-reachable negative cycles; for DAGs, topological ordering lets each edge be relaxed just once. On small graphs, manually writing down distances and predecessors round by round is easier than memorizing three templates and reveals errors in assumptions more clearly.

The graph algorithm concludes here. The next chapter shifts to sorting, exploring how comparisons and movements differ across various strategies: Chapter 9: Basic Sorting.