Shortest Paths I: Dijkstra & Bellman-Ford

What you'll learn

On a weighted graph, "shortest" means cheapest total weight, not fewest edges. Dijkstra's algorithm finds the shortest path from one source to every other vertex — the engine behind GPS routing and network protocols.

By the end you'll be able to:

• Explain edge relaxation, the core operation
• Run Dijkstra with a priority queue
• Know when to switch to Bellman-Ford (negative edges)

Edge relaxation

Every shortest-path algorithm is built on one move: relaxing an edge u → v. If the path to u plus the edge weight beats the best known distance to v, we've found a shorter way — so we update dist[v]. Repeat until nothing improves.

Dijkstra's algorithm

Dijkstra's insight: always settle the nearest unsettled vertex next. Once you pick the closest remaining vertex, its distance is final (no later, longer path can improve it — as long as weights are non-negative). A min-heap keeps "nearest next" fast. Watch the distances converge:

Negative edges & Bellman-Ford

If edges can be negative, Dijkstra's greedy choice breaks — a far-away vertex might become cheaper later. Bellman-Ford handles this by relaxing every edge, V − 1 times over. It's slower at O(V·E), but it also detects negative cycles: if an edge still relaxes on a V-th pass, a negative cycle exists.

In code

import heapq
INF = float("inf")

def dijkstra(graph, start):        # graph: node -> [(neighbor, weight)]
    dist = {start: 0}
    pq = [(0, start)]              # min-heap of (distance, node)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, INF):
            continue               # stale entry, skip
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, INF):
                dist[v] = nd       # relax
                heapq.heappush(pq, (nd, v))
    return dist

Recap & quick check

Dijkstra finds single-source paths. Next: all-pairs paths and a smarter, goal-directed search. Next up: Module 27 — Shortest Paths II & A*.