Graph Algorithms

When to use

• Modeling a problem as a graph and selecting the right traversal or optimization algorithm
• Finding shortest paths with positive weights (Dijkstra), negative weights (Bellman-Ford), or all pairs (Floyd-Warshall)
• Building minimum spanning trees for network design problems
• Resolving task dependency order via topological sort
• Finding strongly connected components for 2-SAT or condensation graphs
• Computing max flow / min cut or bipartite matching for allocation problems
• Pathfinding in grids or maps with a heuristic (A*)

Core principles

1. Representation determines complexity — adjacency list for sparse, matrix for dense; wrong choice costs orders of magnitude
2. Negative weights break Dijkstra — if any edge weight is negative, use Bellman-Ford; don't assume inputs are clean
3. Max-flow = min-cut — network flow problems often hide as cut problems; recognize the dual
4. Topological sort = DP on a DAG — if you can sort topologically, you can compute DP in one pass
5. Kruskal needs Union-Find; Prim needs a heap — pick based on graph density, not familiarity