Shortest Paths & MST Explained: Dijkstra, Bellman-Ford, Prim & Kruskal

Google Maps offers two routes to the airport: 3 turns through a jammed flyover, or 7 turns through empty service roads. BFS would pick the first — fewest hops. Every human picks the second — least time. The moment roads have lengths, counting hops stops answering the real question.

This lesson upgrades BFS for weighted roads (Dijkstra), meets the one input that breaks the upgrade (Bellman-Ford to the rescue), and then answers a different question people constantly confuse with routing: wiring everything together at minimum cost (Prim and Kruskal). Four named algorithms, and — notice — every one of them is a greedy algorithm whose safety someone already proved.

Where BFS's guarantee dies

BFS's promise was: first arrival = fewest edges. Add weights and the promise answers the wrong question — a direct road of cost 10 loses to a two-hop detour of 1 + 2, but BFS reaches the destination via the direct road first and confidently records 10. BFS counts hops; weighted graphs need sums. What would need to change in BFS to fix this?

Dijkstra: serve the cheapest, settle it forever

Look at WHERE BFS's guarantee came from: the queue served vertices in distance order. With weights, a plain queue can't do that — but a min-heap can: always serve the vertex with the smallest total-cost-so-far. That single substitution is Dijkstra's algorithm.

Why does serving-cheapest restore the guarantee? When the heap hands you vertex u at cost d, every other route to u would have to pass through something currently costlier — and (with non-negative weights!) grow from there. Nothing can undercut d later, so u is settled: its answer is final. The improving-updates along the way have a name — relaxation: found a cheaper route to v? Lower v's estimate.

import heapq

def dijkstra(adj, src):               # adj: u -> [(v, weight), ...]
    dist = {src: 0}
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float("inf")):
            continue                  # stale entry - skip (see below)
        for v, w in adj[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd          # RELAX: found a cheaper route
                heapq.heappush(heap, (nd, v))
    return dist

Two Python habits carry the implementation: push improved estimates freely (heapq can't update entries in place), and skip stale pops — the d > dist check discards leftovers whose vertex already settled cheaper. That's the lazy-deletion idiom from the heaps lesson, earning its keep. Cost: O((V + E) log V).

Dry run: every relaxation shown

edges: A->B(4), A->C(1), C->B(2), B->D(1), C->D(5)

pop (0, A): relax B->4, C->1          heap=[(1,C),(4,B)]
pop (1, C): relax B: 1+2=3 < 4 -> B=3 ; D: 1+5=6 -> D=6
                                      heap=[(3,B),(4,B),(6,D)]
pop (3, B): relax D: 3+1=4 < 6 -> D=4
                                      heap=[(4,B),(4,D),(6,D)]
pop (4, B): STALE (dist[B]=3) -> skip
pop (4, D): current -> settled
pop (6, D): stale -> skip

dist = {A:0, C:1, B:3, D:4}

Read the story in it: the direct A→B edge (4) lost to the detour A→C→B (1+2 = 3), and D's first estimate 6 was undercut to 4 via B. Exactly the airport-route correction BFS couldn't make.

One negative edge breaks everything

Go back to the settling argument and find its quiet assumption: "every other route would grow from there." What if an edge could SHRINK a route — a negative weight? (A cashback leg; a downhill that recharges the battery.) Then a path through expensive-then-negative can undercut a vertex Dijkstra already settled — but settled means we stopped listening. Dijkstra with negative edges doesn't crash — it confidently returns wrong answers, the worst failure mode software has.

"Why does Dijkstra fail on negative weights?" is a top-three reported graph question, and now you own the answer: the greedy settle-forever step assumes extending never cheapens, and negative edges break exactly that.

Bellman-Ford: slower, tougher

If settling early is the vulnerability, don't settle: relax EVERY edge, V−1 times. Why V−1? A shortest path visits no vertex twice, so it has at most V−1 edges — and each full pass locks in all shortest paths one edge longer than the last pass did. After V−1 passes, every shortest path (negatives included) has been found.

def bellman_ford(n, edges, src):    # edges: (u, v, w)
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    for _ in range(n - 1):           # V-1 rounds of relax-everything
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:            # a V-th round: anything STILL improving?
        if dist[u] + w < dist[v]:
            return None              # negative CYCLE: "shortest" undefined
    return dist

Price: O(V·E) versus Dijkstra's near-linearithmic — robustness costs. Bonus: if a V-th pass still improves something, the graph has a negative cycle — a loop you could ride forever decreasing cost, so "shortest" doesn't exist. Currency-arbitrage detection is literally this check.

A different question: spanning trees

New scenario, different question. Connect 6 villages with optical fibre. Nobody asks how far village A is from village B along the network — only that everything is connected, at minimum total cable cost.

The cheapest connector has a forced shape: it's a tree — any cycle contains a removable edge (the network stays connected without it), so the optimum has none. Connected + acyclic on V vertices means exactly V−1 edges — the tree theorem cashing in. This cheapest connector is the minimum spanning tree (MST).

Shortest path optimises routes between points; MST optimises total connection cost. The MST path between two villages can be long — that's fine; nobody promised routes. Mixing these two questions up is the classic error this topic exists to test.

Prim vs Kruskal

Two greedy strategies, both provably optimal (exchange arguments again), different growth patterns:

Kruskal: sort ALL edges by weight; take each unless it would close a cycle; stop at V−1 taken. A forest of islands merging. And the cycle check? "Would this edge connect two already-connected vertices?" — that is verbatim union-find's question: same root → reject. DSU's promised second algorithm, delivered. O(E log E), dominated by the sort.

Prim: grow ONE tree from any start; keep a min-heap of edges leaving the tree; repeatedly absorb the cheapest outside neighbour. Structurally Dijkstra's twin — same heap loop, one line different: the key is the single edge weight into the tree, not the accumulated distance from a source. O(E log V).

Practical selection: sparse graph, edges easy to sort → Kruskal; dense or adjacency-list-native → Prim. Same total weight either way (edge sets may differ under ties).

What if...?

What if I need the actual route, not just distances? Keep a parent map: whenever relaxation improves dist[v] via u, record parent[v] = u; walk parents backward from the target and reverse. Works identically for BFS and Bellman-Ford.

What if the graph is disconnected? Unreachable vertices simply never enter dist (Dijkstra) or stay INF (Bellman-Ford) — report them as unreachable rather than crashing on a missing key. For MST: no spanning tree exists; Kruskal ends with fewer than V−1 edges — check it.

What if all weights are equal? Then hop-count IS the cost — Dijkstra collapses into an expensive BFS. Use BFS; using Dijkstra anyway is correct but signals you didn't notice.

What if negative edges exist but no negative cycles? Bellman-Ford handles it exactly; Dijkstra stays broken. And if negative cycles exist, no algorithm can define "shortest" — detection (Bellman-Ford's V-th pass) is the only honest answer.

Common mistakes

• Running Dijkstra on graphs with negative edges — wrong answers, no error.
• Confusing MST with shortest paths — different questions, different algorithms, different outputs.
• Trying to update priorities inside heapq — push duplicates and skip stale pops instead.
• Forgetting Kruskal's stop condition (V−1 edges) and scanning on pointlessly.
• Claiming Bellman-Ford "handles" negative cycles — it detects them; nothing can route through one.
• Using Dijkstra on unweighted graphs where BFS suffices.

Choosing the algorithm: the decision table

Choose by constraint, never by speed ranking: the fastest algorithm that tolerates your graph's properties. Saying that sentence, then reading the table, is the complete interview answer.

Quick revision

One thing to remember

Dijkstra is BFS with a min-heap, and its one blind spot is negative edges — while MST is a different question entirely: connect everything, not route between points.

Practice Zone — PYQs from real selection rounds

Six MCQs, then two full traces: Dijkstra with every heap operation shown, and Kruskal accepting and rejecting edges by hand.

Q1Dijkstraeasy

BFS finds shortest paths in unweighted graphs. Dijkstra exists because:

Asked in

aBFS is too slowbWith WEIGHTED edges, fewest edges ≠ smallest total weight — a 2-hop route of 1+1 beats a 1-hop route of 10cBFS cannot handle directed graphsdDijkstra uses less memory

Q2Dijkstramedium

Dijkstra's algorithm fails with NEGATIVE edge weights because:

Asked in

aDistances cannot be negative numbersbIt finalises a node greedily, assuming no future route can undercut it — a negative edge later can, invalidating the finalised answercThe priority queue rejects negative keysdIt doesn't fail; it just runs slower

Q3MSTeasy

A minimum spanning tree of a connected weighted graph is:

Asked in

aThe shortest path between the two farthest nodesbA subset of edges connecting ALL vertices with minimum total weight (and no cycles — it's a tree, V−1 edges)cThe tree with the fewest leavesdAny tree containing the minimum-weight edge

Q4MSTmedium

Kruskal's algorithm sorts edges by weight and adds each unless it creates a cycle. The cycle check uses:

Asked in

aDFS from scratch per edgebUnion-find: an edge whose endpoints share a root would close a cycle — skip it; otherwise union themcA visited setdCounting edges

Q5MSTmedium

Prim vs Kruskal — the practical difference is:

Asked in

aThey can produce different total weightsbPrim GROWS one tree outward from a start node (heap of frontier edges); Kruskal merges a FOREST by global cheapest edges — Prim suits dense graphs, Kruskal sparse ones with edges easily sortedcPrim only works on directed graphsdKruskal ignores weights

Q6Shortest pathshard

For flight prices with occasional CASHBACK legs (negative weights) and a need to detect exploitable money-making loops, you should use:

Asked in

aDijkstra — it is the fastestbBellman-Ford — it tolerates negative edges and its V-th relaxation pass detects negative cyclescBFS — flights are just hopsdKruskal — build the MST of cheap flights

Hands-on tasks:

FAQ

Routes and networks priced. Next, we drop below the structures entirely — numbers as rows of switches — Lesson 11: Bit Manipulation →