Graph Algorithms: Dijkstra, Bellman-Ford, Kruskal and Prim

Graph algorithms solve problems on networks of points connected by lines — roads between cities, cables between computers, friendships between people. The four essentials are Dijkstra and Bellman-Ford, which find the shortest route from one point to all others, and Kruskal and Prim, which connect every point as cheaply as possible.

They matter because almost every modern system is a graph: map apps route you with shortest-path algorithms, and network engineers lay the cheapest possible cable with minimum spanning trees. Picking the wrong one — Dijkstra on negative weights, for instance — gives silently wrong answers.

Key Concepts

• Vertex: a point in the graph, like a city. Edge: a connection with a weight (cost, distance, time).
• Relaxation: the core shortest-path step — if reaching v through u is cheaper than the current best distance to v, update it.
• Negative weight: an edge with negative cost. Dijkstra cannot handle these; Bellman-Ford can.
• Negative cycle: a loop with negative total weight, where shortest paths are undefined. Bellman-Ford detects it.
• Spanning tree: edges connecting all vertices with no cycles — always exactly V − 1 edges.
• Minimum spanning tree (MST): the spanning tree with the smallest total weight.
• Cut property: the cheapest edge crossing any split of the vertices belongs to some MST — what Kruskal and Prim rely on.

Formulas

• Relaxation: d[v] = min(d[v], d[u] + w(u, v)), where d[x] is the best known distance from the start and w(u, v) is the edge weight, in km, minutes, or rupees.
• Dijkstra: O((V + E) log V) with a binary heap. Requires non-negative weights.
• Bellman-Ford: O(V × E). Relaxes every edge V − 1 times; one more pass that still relaxes an edge proves a negative cycle.
• Kruskal: O(E log E), dominated by sorting edges, plus near-constant union-find steps.
• Prim: O((V + E) log V) with a binary heap.

Worked Example

Dijkstra from A. Edges: A–B 4, A–C 2, C–B 1, B–D 5, C–D 8, D–E 2, C–E 10. Distances start at infinity except A = 0:

1. Visit A (0): B = min(∞, 4) = 4, C = min(∞, 2) = 2.
2. Visit C (2): B = min(4, 3) = 3; D = 10; E = 12.
3. Visit B (3): D = min(10, 8) = 8.
4. Visit D (8): E = min(12, 10) = 10. Visit E (10).
5. Final: A = 0, B = 3, C = 2, D = 8, E = 10. Shortest path to E: A → C → B → D → E costs 2 + 1 + 5 + 2 = 10 ✓.

Common Misconceptions

• "Dijkstra works on any graph." It fails with negative weights, because a finished vertex is never revisited even if a negative edge later offers a cheaper route. Use Bellman-Ford there.
• "Kruskal and Prim give the same tree." They give the same total weight, but with tied edge weights the edge sets can differ — both are valid MSTs.
• "Shortest path and MST are the same." Shortest path minimises each route from the source; an MST minimises total wiring. Different questions, different answers.

Real-World Applications

• Navigation: map apps run shortest paths over road graphs with travel-time weights.
• Network design: laying fibre at minimum cost is an MST problem.
• Currency arbitrage: Bellman-Ford detects negative cycles, i.e. profitable trade loops.
• Social networks: degrees of separation are shortest-path queries.

Dijkstra is the default for shortest routes with non-negative costs; Bellman-Ford takes over with negative weights and flags negative cycles. Kruskal and Prim answer the other great question — the cheapest way to connect everything — building it greedily one safe edge at a time.