Graph Algorithm Applicability - Choosing the Right Tool for the Graph

Helpful context:

• Graph Algorithms & Traversal - Maps, Networks, and Hidden Order
• Minimum Spanning Trees & Union-Find - Spanning a World on a Budget
• Shortest Paths - When Greed Works and When It Doesn’t
• Network Flow & Matching - The Max, the Min, and Why They’re Equal

We’ve covered a lot of graph algorithms at this point. BFS, DFS, topological sort, Kosaraju’s, Kruskal’s, Prim’s, Dijkstra’s, Bellman-Ford, Floyd-Warshall, max flow - the list is long. But knowing an algorithm exists is only half the battle. The harder question is: given a problem and a graph in front of us, which one do we reach for?

The answer isn’t arbitrary. Each algorithm was designed with assumptions about the graph’s structure baked in. Use an algorithm on the wrong kind of graph and it either gives wrong answers or runs forever. The good news: the decision tree is fairly short once we know what to look for.

This post is a reference - come back to it whenever a graph problem needs untangling.

The Graph Properties That Matter

Before picking an algorithm, we need to pin down four properties of the graph:

1. Directed or undirected? In an undirected graph, every edge goes both ways. In a directed graph (digraph), edges are one-way streets. Many algorithms are defined for one but not the other, and applying them to the wrong type is a common source of bugs.

2. Weighted or unweighted? Weights on edges represent cost, distance, or capacity. Algorithms designed for weighted graphs can run on unweighted ones (just set all weights to 1), but the reverse doesn’t work - you can’t feed an unweighted algorithm a graph where the edge costs actually matter.

3. Does it contain cycles? A directed graph with no cycles is a DAG. Several algorithms rely on processing vertices in topological order, which only exists when there are no cycles. If the graph has a cycle, those algorithms are off the table.

4. Are any edge weights negative? Negative weights are perfectly legal in many real settings - think profit vs. cost, or altitude changes on a map. But they silently break algorithms that assume once a vertex is settled, it can’t be improved further.

The Reference Table

Why Each Constraint Exists

These constraints aren’t footnotes - they’re the reason the algorithms work at all. Understanding the why is what lets us reason confidently rather than just memorise a table.

Why do topological sort and DAG-DP require a DAG?

Both algorithms process vertices in dependency order - each vertex is handled only after all its predecessors are done. That ordering only exists when the graph has no cycles. If vertex A depends on B and B depends on A, there’s no valid place to start. DFS detects cycles precisely for this reason: we run it first to confirm topological sort is even applicable.

Why does Dijkstra’s fail on negative weights?

Dijkstra’s greedy step finalises a vertex the moment it’s extracted from the priority queue, on the assumption that no cheaper path to it will ever show up. A negative-weight edge breaks that assumption - it can always produce a cheaper path through a vertex we already marked as done. Here’s the classic example:

Dijkstra finalises C via A→C (cost 2) before it even processes B. But A→B→C costs 1 + (-3) = -2, which is cheaper. The answer is wrong, and there’s no way to detect it from inside the algorithm. Bellman-Ford avoids this by relaxing every edge $V-1$ times with no greedy finalisation, so earlier mistakes get corrected in later rounds.

Why do MST algorithms require undirected graphs?

A spanning tree connects all vertices using edges that can be traversed in either direction - that’s inherently an undirected concept. In a directed graph, the equivalent problem is a minimum spanning arborescence (a directed tree rooted at one vertex, edges pointing away from the root). That requires Edmonds' algorithm (Chu-Liu/Edmonds'), which is significantly more complex. Kruskal’s and Prim’s simply assume we can use each edge both ways.

Why does Bellman-Ford require no negative cycles?

A negative cycle is a cycle whose total edge weight is negative. If a shortest path passes through one, we can always make it cheaper by going around the cycle one more time - there’s no finite minimum. Bellman-Ford detects this situation: after $V-1$ relaxation rounds, if any distance can still be reduced, a negative cycle exists. The shortest path problem is simply undefined in that case.

Why does max flow require a directed graph?

Flow has a direction - it moves from source to sink. An undirected edge between $u$ and $v$ would mean flow could go either way simultaneously, which doesn’t map cleanly to the flow model. Undirected flow problems are converted to directed ones by replacing each undirected edge with two directed edges sharing capacity.

Decision Guide

When a graph problem comes up, working through these questions in order usually narrows it down quickly:

Summary

The constraints in graph algorithms aren’t arbitrary restrictions - each one reflects a genuine mathematical assumption the algorithm relies on. Once we understand why a constraint exists, we know both when to apply the algorithm and what will silently go wrong when we don’t.

Read next:

• PageRank & Power Iteration - Importance as a Fixed Point of a Random Walk