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
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 storage and suit sparse graphs. An adjacency matrix uses storage, provides constant-time edge lookup, and can simplify dense all-pairs algorithms. Complexity statements are incomplete without this choice.
Reading the contracts
V counts all vertices, including isolated ones; E counts edges (an undirected adjacency list stores two entries per edge). The heap bounds in the table use simple graphs; lazy heaps on multigraphs may require log E instead of log V. Include O(V) initialization when E is zero or many vertices are isolated. BFS gives minimum total cost for equal nonnegative edge weights, not for negative costs.
A missing edge is not an edge of weight zero. Store unreachable distances as infinity and distinguish “no path” from a zero-length source-to-itself path. A negative cycle matters only when the source can reach it and it can reach the destination. For undirected shortest walks, a reachable negative edge already permits an arbitrarily negative back-and-forth walk; MSTs do not have this issue because their outputs are acyclic.
For a concrete objective distinction, use the triangle with weights A—B:2, B—C:2, A—C:3. Its MST costs 4, but its A-to-C tree path costs 4 rather than the shortest distance 3. The shortest-path tree rooted at A costs 5 in total.