Graphs: traversal, shortest paths and union–find

Graph questions are usually easy once the graph is identified, and identifying it is the difficulty: currencies and exchange rates, instruments and dependencies, states and transitions. The algorithms themselves are a short list chosen by two properties — are the edges weighted, and can the weights be negative.

Aspect	BFS	DFS
Explores	Level by level	As deep as possible first
Uses	A queue	A stack, or recursion
Finds	Shortest path in an unweighted graph	Any path; cycles; topological order
Memory	The whole frontier — can be wide	The current depth
Good for	Minimum hops, level structure	Connectivity, ordering, backtracking

Table 4.1 · BFS against DFS. BFS finds the shortest path only when every edge has the same weight — which is exactly when it is Dijkstra with a queue instead of a heap.

Algorithm	Handles	Complexity
BFS	Unweighted	$O(V + E)$
Dijkstra	Non-negative weights	$O((V+E)\log V)$ with a heap
Bellman–Ford	Negative weights; detects negative cycles	$O(VE)$
Floyd–Warshall	All pairs	$O(V^3)$
A*	Single target, with a heuristic	Depends on the heuristic

Table 4.2 · Shortest paths. The Bellman–Ford row is the one with a financial use: taking negative logs of exchange rates turns a triangular arbitrage into a negative cycle, which Bellman–Ford detects directly.

Why Dijkstra breaks on negative edges. Dijkstra finalises a node as soon as it is the closest unvisited one, on the reasoning that no later path could be shorter — every remaining edge only adds distance. A negative edge destroys that reasoning: a longer detour can come back cheaper, so a node finalised early may be wrong and nothing ever revisits it. Bellman–Ford makes no such commitment and simply relaxes every edge $V-1$ times, which is slower and correct. If a further relaxation still improves something, there is a negative cycle.

Figure 4.3 · The three-edge counterexample to Dijkstra. Dijkstra would finalise A at distance 2 before visiting B at distance 5. But the route Start → B → A costs 5 − 4 = 1. A later negative edge invalidates the assumption that a finalised distance cannot improve.

Figure 4.4 · Why negative edges are expensive. On a sparse graph with four edges a vertex. Bellman–Ford is the price of admitting negative weights — and you pay it deliberately, because detecting a negative cycle is how a triangular arbitrage is found in a currency graph.

Graphs: traversal, shortest paths and union–find

After this lesson you should be able to

The rest of this lesson is in Premium