The plain BFS from the Graphs hub finds shortest paths only because it assumes every edge costs the same one step. Put weights on the edges, ask for the cheapest way to connect everything, or demand a valid ordering, and that assumption collapses — and each specific way it collapses has a named algorithm invented for it. This category is a tour of five: Dijkstra for weighted shortest paths, the minimum-spanning-tree pair (Prim and Kruskal), Bellman-Ford for when Dijkstra’s greed fails, topological sort for orderings, and Hierholzer’s for Eulerian paths. Each one rests on an assumption the plain traversal couldn’t make, and the interesting part is exactly where each assumption holds and where it breaks.
Dijkstra: shortest path once edges have weight
When edges carry non-negative weights, BFS’s “nearest by hop count” is wrong and Dijkstra’s “nearest by total cost” is right. It’s BFS with a min-heap instead of a plain queue: always expand the unfinished node with the smallest distance so far, relax its neighbors, and because you always finalize the closest remaining node, each is settled once.
// long distances + comparingLong so summed weights can't overflow the heap order
PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[1])); // {node, dist}
long[] dist = new long[n]; Arrays.fill(dist, Long.MAX_VALUE); dist[src] = 0;
pq.offer(new long[]{src, 0});
while (!pq.isEmpty()) {
long[] top = pq.poll(); int u = (int) top[0]; long d = top[1];
if (d > dist[u]) continue; // stale entry, already settled
for (int[] e : adj.get(u)) { // e = {neighbor, weight}
long nd = d + e[1];
if (nd < dist[e[0]]) { dist[e[0]] = nd; pq.offer(new long[]{e[0], nd}); }
}
}Network Delay Time is Dijkstra straight — the answer is the largest of the shortest distances (or -1 if any node is never reached), the moment the last node hears the signal. Swim in Rising Water is Dijkstra with the cost function bent: instead of summing edge weights you minimize the maximum elevation along a path, so the heap orders by the worst cell a route has crossed.
Minimum spanning tree: connect everything for the least
Min Cost to Connect All Points asks for the cheapest set of edges that ties every node together with no cycle — a minimum spanning tree. Two classic algorithms build it. Prim grows one tree outward, repeatedly pulling the cheapest edge leaving it from a min-heap, which feels a lot like Dijkstra with a different key. Kruskal instead sorts every edge by weight and adds each one unless it would close a cycle, using union-find to detect that in near-constant time. Either works; Prim tends to suit dense graphs and Kruskal sparse ones.
When Dijkstra’s greed is a trap
Dijkstra only works because finalizing the closest node can never be regretted — and add a constraint and that stops being true. Cheapest Flights Within K Stops caps the number of hops, so a route that’s cheap now might be forbidden later for using a stop too many, and finalizing each node from a single best distance — the thing plain Dijkstra does — breaks. (A Dijkstra that expands (node, hops-used) states stays valid; it just tracks more state.) The cleaner fix is Bellman-Ford: relax every edge k + 1 times, letting cost information ripple out one hop per round — but only if each round relaxes from a snapshot of the previous round’s distances. Relax in place and a single sweep can chain several edges together and blow past the stop budget, so you copy dist before each of the k + 1 sweeps. It also tolerates negative edges Dijkstra can’t. The bounded version here costs — k stops means up to k + 1 edges, and each of those sweeps copies the V-size snapshot and relaxes every edge — where full Bellman-Ford runs ; either way it’s the right tool when a greedy shortest path would cut a corner it isn’t allowed to.
Ordering and one-line traversals
Two problems aren’t about distance at all. Alien Dictionary reconstructs an unknown alphabet from a sorted word list: each adjacent pair of words reveals one ordering constraint at their first differing letter, and a topological sort of those constraints yields the alphabet — reporting a contradiction if they form a cycle, or if an earlier word strictly contains the next as a prefix (like ["abc", "ab"]), which is invalid even with no cycle at all. Reconstruct Itinerary wants a path that uses every ticket exactly once — an Eulerian path — and specifically the lexicographically smallest one, so Hierholzer’s algorithm walks until it’s stuck and splices in detours while always taking the next destination in sorted order (a min-heap or pre-sorted adjacency per airport).
The algorithms behind the network
The weighted-graph algorithms run the networks this page reached you over. Link-state routing protocols like OSPF have every router build a map of the network and run Dijkstra to compute its shortest-path forwarding table, while distance-vector protocols like RIP use Bellman-Ford directly and BGP layers policy onto a path-vector descendant of the same idea. Minimum spanning trees are the math behind laying the least cable or pipe to reach every site, and topological sort schedules any pipeline of tasks with dependencies. When I actually need one of these I reach for a graph library rather than reimplement Dijkstra under pressure — but knowing which algorithm a problem maps to is what lets me pick the right library call and predict its cost instead of guessing.
It comes down to assumptions
What actually separates these algorithms is what each one is allowed to assume. Dijkstra trusts that the closest unfinished node is settled for good — true under non-negative weights, false the moment a hop limit or a negative edge enters, which is where Bellman-Ford takes over. Kruskal trusts that the cheapest edge that doesn’t form a cycle is always safe to add. A topological sort trusts the graph has no cycle at all, and reports failure when it finds one. So the question to ask isn’t “what graph algorithm is this” but “which algorithm’s assumption do this problem’s constraints actually satisfy” — and then to check that assumption still holds before trusting the answer.
References
- NeetCode 150 — Advanced Graphs — six problems and the classic algorithms each maps to.
