Graph Algorithms

Start by specifying the graph: directed or undirected, weighted or unweighted, sparse or dense, and whether negative edges or cycles are possible. Then state the output—reachability, one path, all distances, or a connecting subgraph.

Decision map

Problem	Conditions	Algorithm	Time with common representation
Reachability / structure	general adjacency lists	DFS or BFS	$O(V+E)$
Minimum-edge path	unweighted / equal edge costs	BFS	$O(V+E)$
Single-source shortest paths	nonnegative weights	Dijkstra	$O((V+E)\log V)$
Single-source shortest paths	negative edges allowed	Bellman–Ford	$O(VE)$
All-pairs shortest paths	dense or modest $V$	Floyd–Warshall	$O(V^3)$
Minimum spanning tree	weighted undirected graph	Prim	$O(E\log V)$
Minimum spanning tree	sortable edge list	Kruskal	$O(E\log E)$

Keep the objectives separate

A shortest-path tree minimizes source-to-vertex distances. A minimum spanning tree minimizes the total weight needed to connect all vertices. Neither objective implies the other, even though Dijkstra and Prim both use a priority queue.

Representation matters

Adjacency lists use $O(V+E)$ storage and suit sparse graphs. An adjacency matrix uses $O(V^2)$ storage, provides constant-time edge lookup, and can simplify dense all-pairs algorithms. Complexity statements are incomplete without this choice.

Sources

• MIT OpenCourseWare: Introduction to Algorithms
• Open Data Structures: Graphs