Weighted Graphs: Picking the Right Algorithm

What changes when edges have weights

A weighted graph attaches a cost to every edge — a flight price, a network delay, a difficulty. That one change breaks plain BFS. BFS explores in rings of "one edge away, two edges away, ...", so the first time it reaches a node is via the fewest edges — not the cheapest total.

Concrete failure: A connects to B directly with weight 10, and A connects to C (weight 1) which connects to B (weight 2). BFS reaches B first through the direct edge — one hop — and declares the answer 10. The real cheapest path is A → C → B, cost 3, using two hops. Once weights exist, hop count and cost are different quantities, and you need an algorithm that tracks cost.

This module is about four such algorithms and — just as important — the problem-statement signals that tell you which one to reach for.

Dijkstra: greedy lock-in with a min-heap

Dijkstra's algorithm answers "cheapest path from one source to everything" when all weights are non-negative. The idea is greedy: among all nodes whose best-known distance is still tentative, the one with the smallest tentative distance can never be improved — any other route to it would have to pass through something already at least as far. So you lock it in, then relax its neighbors (relaxing means: check whether going through this node gives a neighbor a better distance than it had, and if so, update it).

A min-heap (a structure that always hands you its smallest item in O(log n)) keeps "which tentative node is closest" cheap to answer:

import heapq

def dijkstra(n, adj, src):
    dist = [float("inf")] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue                # stale entry — already found better
        for nb, w in adj[node]:
            if d + w < dist[nb]:
                dist[nb] = d + w
                heapq.heappush(heap, (dist[nb], nb))
    return dist

Two details interviews test. First, a node's distance is final when it is popped, not when it is pushed — the heap may hold several outdated entries for one node, and the d > dist[node] line skips the stale ones. Second, the complexity is O((V + E) log V) with a binary heap: every edge can push one heap entry.

The greedy proof leans entirely on non-negative weights. A negative edge could make a "farther" route cheaper after Dijkstra already locked a node in — so negative weights mean Dijkstra is off the table.

Variant: minimize the biggest step, not the sum

Some problems score a path by its worst moment instead of its total: "swim across the grid so the deepest water you ever enter is as shallow as possible" (Swim in Rising Water), or "minimize the maximum effort of any single step". The Dijkstra skeleton survives untouched — only the priority changes. Instead of d + w, a candidate path's score is max(d, w): the worst step so far. Everything else — heap, lock-in, relaxation — stays identical. This "same machine, different priority" move also handles maximizing probability products.

Bellman-Ford: when hops are constrained (or weights go negative)

Cheapest Flights Within K Stops adds a rule Dijkstra cannot respect: at most K intermediate stops. Dijkstra finalizes each node once, at its cheapest cost — but the cheapest route to a node might use too many hops, and a pricier-but-shorter route that the stop limit requires gets discarded.

Bellman-Ford relaxes every edge, in rounds. After round r, dist[v] is the cheapest path to v using at most r edges. That per-round hop guarantee is exactly what a K-stop limit needs — run K + 1 rounds (K stops means K + 1 flights) and read the answer:

def cheapest(n, flights, src, dst, k):
    dist = [float("inf")] * n
    dist[src] = 0
    for _ in range(k + 1):
        nxt = dist[:]              # snapshot: no chaining inside a round
        for u, v, w in flights:
            if dist[u] + w < nxt[v]:
                nxt[v] = dist[u] + w
        dist = nxt
    return dist[dst]

The snapshot copy matters: relaxing into the same array would let one round chain several edges together, breaking the "at most r edges" meaning. Cost: O(K · E) here, O(V · E) in the general algorithm. Bellman-Ford also handles negative edge weights correctly, which Dijkstra never can.

Prim's: cheapest way to connect everything

A minimum spanning tree (MST) is a different question entirely: not "cheapest route from A to B" but "cheapest set of edges that connects all nodes into one component". Min Cost to Connect All Points is the classic.

Prim's algorithm is Dijkstra with a one-line edit. Grow a tree from any start node; at each step, add the cheapest single edge that connects a new node to the tree. The heap priority is the individual edge weight, not the cumulative distance from the source — the tree does not care how far a node is from the start, only how cheaply it can be attached.

The alternative, Kruskal's, sorts all edges globally and adds each one unless it would form a cycle (checked with union-find). Both give an MST; Prim's is usually cleaner on dense point-cloud inputs.

Hierholzer's: use every edge exactly once

Reconstruct Itinerary hands you flight tickets and asks for an itinerary that uses every ticket exactly once. That is an Eulerian path — a walk consuming every edge once (contrast with visiting every node). Hierholzer's algorithm: DFS from the start, consuming edges as you go; when you hit a dead end (no unused edges), append that node to the route and back up. The route comes out reversed, so flip it at the end. For "smallest lexical itinerary", keep each node's destination list sorted and always consume the alphabetically smallest ticket first. Every edge is consumed once, so it runs in O(E log E) including the sort.

The decision table

Alien Dictionary rounds out the set: adjacent words in a sorted alien dictionary reveal letter precedences (the first differing character pair is a directed edge), and topological sort — covered in the graphs module — turns those edges into an alphabet, or reports a cycle meaning no valid order exists. One edge case: if a later word is a strict prefix of an earlier word (like "abc" before "ab"), the input is invalid before any sorting starts.