P-5.6 Graph Algorithms

What this is and why it exists

This is where the data structures and the design techniques come together. A small number of named algorithms cover an enormous share of real problems.

One selection rule is worth memorising outright, because it is about edge weights and it decides which algorithm is even correct. Unweighted graphs need only a breadth-first traversal. Non-negative weights want Dijkstra. Negative weights force Bellman-Ford.

Reaching for the wrong one produces answers that look reasonable and are not. That is why the rule is worth memorising rather than re-deriving under pressure.

The vocabulary

• Traversal — visiting every reachable vertex in some order.
• Depth-first — going as deep as possible before backing up.
• Breadth-first — visiting everything one step away, then two, and so on.
• Connected component — a group of vertices all reachable from each other.
• Topological order — an order in which every task follows its prerequisites.
• Shortest path — the least total edge cost between two vertices.
• Settled — a vertex whose shortest distance is considered final.
• Negative cycle — a loop whose total cost is below zero.

The mental model

Depth-first traversal goes as deep as it can before backing up. It is naturally recursive and very short to write. It is what you use to detect cycles, find connected components, and order dependencies.

Breadth-first visits everything one step away, then everything two steps away. Because of that order, it reaches each vertex by the fewest edges possible. When there are no weights, that already is the shortest-path answer, and no further algorithm is needed. It uses a queue, which is the arrival-order structure from the previous module doing exactly the job it was described for.

Ordering dependent tasks is the same problem three times over: a build order, a course prerequisite listing, a spreadsheet recalculation. Each is a graph, and the answer is a topological order. If the graph contains a cycle then no valid order exists, and a correct algorithm reports that rather than guessing at one. That reporting is the useful part — a circular dependency is a real finding.

Dijkstra always expands the nearest unfinished vertex. That gives shortest paths whenever no edge has negative cost, and the heap from the previous module is what makes it efficient. Note the connection: a heap answers "what is the smallest thing left", which is precisely the question Dijkstra asks at every step.

And now the reason the selection rule matters. Dijkstra assumes that once a vertex is settled, nothing can improve it. A negative edge breaks that assumption directly, because a longer route can become cheaper later on. So Dijkstra does not merely run slowly on such a graph. It returns a wrong answer, confidently. Bellman-Ford handles negative weights and additionally detects negative cycles, which are the case where no shortest path exists at all.

What you should now be able to explain or do

Implement both traversals and say what each is good at. Explain why breadth-first gives shortest paths when edges are unweighted. Produce a topological order, and report a cycle rather than guessing. Use Dijkstra with a heap, and say why a heap is the natural fit. State why Dijkstra is wrong on negative weights, and what Bellman-Ford adds.

Check yourself