Shortest Paths (Dijkstra’s Algorithm)

Updated

October 31, 2026

Shortest Paths (Dijkstra’s Algorithm)

While Breadth-First Search finds the route with the fewest intermediary hops, real-world networks involve weighted costs: transmission latencies, courier miles, road tolls, or dispatch fees. Dijkstra’s algorithm calculates the lowest total cost path across a weighted graph with non-negative edge weights in \(O((V + E) \log V)\) time using a min-priority queue. In Python, the boring default is to pair standard dictionaries with the C-accelerated heapq module.

Graph Traversal and Dijkstra Relaxation

Mental model

Dijkstra maintains: 1. dist[node]: The lowest accumulated cost from the start node to each destination (initialized to \(\infty\), with dist[start] = 0). 2. prev[node]: The preceding node along the cheapest known path.

At each step, the algorithm pops the unvisited vertex \(u\) with the smallest known distance from a min-priority queue and relaxes all of its outgoing edges \((u, v, \text{weight})\):

\[\text{If } \text{dist}[u] + \text{weight} < \text{dist}[v] \implies \text{dist}[v] = \text{dist}[u] + \text{weight}\]

Edge Relaxation:
(Depot) --[Known: 2]--> (Hub A) --[Weight: 3]--> (Dest)
                           \                        ^
                            \--[Weight: 1]-->(Hub B)-[Weight: 1]-/

Direct path: Depot -> Hub A -> Dest = 2 + 3 = 5
Relaxed path: Depot -> Hub A -> Hub B -> Dest = 2 + 1 + 1 = 4 (Cheaper!)

Because edge costs are non-negative, the moment a vertex is popped from the min-priority queue, its calculated distance is provably optimal.

Worked examples

Case 1: Delivery Network Optimization with heapq

Save as dijkstra_delivery.py. Calculate the lowest-latency delivery route between warehouse dispatch depots.

# dijkstra_delivery.py
import heapq
from dataclasses import dataclass


@dataclass(slots=True)
class Edge:
    to: str
    weight: int


class WeightedGraph:
    def __init__(self) -> None:
        self.adj: dict[str, list[Edge]] = {}

    def add_edge(self, u: str, v: str, weight: int) -> None:
        self.adj.setdefault(u, []).append(Edge(to=v, weight=weight))
        self.adj.setdefault(v, []).append(Edge(to=u, weight=weight))

    def dijkstra(self, start: str, dest: str) -> tuple[int, list[str]] | None:
        dist: dict[str, int] = {node: float("inf") for node in self.adj}
        dist[start] = 0
        prev: dict[str, str] = {}

        # Min-priority queue stores tuples: (accumulated_dist, node)
        pq: list[tuple[int, str]] = [(0, start)]

        while pq:
            curr_dist, u = heapq.heappop(pq)

            # Drop stale queue entries
            if curr_dist > dist[u]:
                continue

            if u == dest:
                break  # Destination reached with optimal distance

            for edge in self.adj.get(u, []):
                new_dist = curr_dist + edge.weight
                if new_dist < dist.get(edge.to, float("inf")):
                    dist[edge.to] = new_dist
                    prev[edge.to] = u
                    heapq.heappush(pq, (new_dist, edge.to))

        if dist.get(dest) == float("inf"):
            return None  # Destination unreachable

        # Reconstruct path
        path: list[str] = []
        curr: str | None = dest
        while curr is not None:
            path.append(curr)
            curr = prev.get(curr)

        path.reverse()
        return dist[dest], path


def main() -> None:
    network = WeightedGraph()
    network.add_edge("Main-Depot", "North-Hub", 4)
    network.add_edge("Main-Depot", "South-Hub", 2)
    network.add_edge("South-Hub", "North-Hub", 1)
    network.add_edge("North-Hub", "Airport-Station", 7)
    network.add_edge("South-Hub", "Midtown-Annex", 8)
    network.add_edge("North-Hub", "Midtown-Annex", 3)
    network.add_edge("Midtown-Annex", "Airport-Station", 1)

    result = network.dijkstra("Main-Depot", "Airport-Station")
    assert result is not None
    min_cost, path = result

    print(f"Lowest Delivery Latency: {min_cost} ms")
    print("Optimal Route: " + " -> ".join(path))


if __name__ == "__main__":
    main()

Run:

uv run python dijkstra_delivery.py

Output:

Lowest Delivery Latency: 7 ms
Optimal Route: Main-Depot -> South-Hub -> North-Hub -> Midtown-Annex -> Airport-Station

Although the direct hop Main-Depot -> North-Hub -> Airport-Station has fewer stops (2 hops, cost 11), Dijkstra discovers the 4-hop route via South-Hub and Midtown-Annex with total cost \(2 + 1 + 3 + 1 = 7\).

The trap

The two fatal traps with Dijkstra’s algorithm:

  1. Negative Edge Weights: If an edge weight is negative (e.g., a cashback discount that reduces total cost), Dijkstra’s greedy invariant breaks, leading to wrong answers or infinite loops. Graphs with negative edge weights require the Bellman-Ford algorithm.
  2. Missing the Stale Item Check: Because Python’s heapq does not support updating keys in place, you push a new (new_dist, v) tuple every time a shorter path to \(v\) is discovered. Omitting if curr_dist > dist[u]: continue forces the loop to re-process superseded paths, turning an \(O((V+E)\log V)\) algorithm into an inefficient crawl.

The boring rule

  1. Use BFS for unweighted graphs. Use Dijkstra when edges have non-negative numerical weights.
  2. Store (distance, node_id) tuples in heapq so Python sorts by distance automatically.
  3. Always include if curr_dist > dist[u]: continue at the beginning of the pop loop.
  4. Stop the search immediately once the destination node is popped from the heap.

Try this

  1. Modify dijkstra to return a dictionary of shortest distances to all reachable nodes from start.
  2. Add an edge filter parameter to Dijkstra that excludes any route traversing through congested toll roads.