Graph algorithms turn edges into answers about reachability, dependency order, path cost, connectivity, or capacity. The required output comes first. Direction, weight semantics, and input density then narrow the valid choices. Breadth-first search finds a minimum-hop route, while Dijkstra minimizes total weight and becomes invalid as soon as an edge can be negative.
Diagram
flowchart TD A[Graph problem] --> B{Need reachability or levels} B -->|Yes| C[DFS BFS] B -->|No| D{Need minimum path cost} D -->|Yes with non negative weights| E{Have a heuristic to the target} E -->|Yes| E1[A Star Search] E -->|No| E2[Dijkstra] D -->|Can have negative edges| F[Bellman Ford] D -->|Need all pairs shortest paths| G[Floyd Warshall] A --> H{Need structure not distance} H -->|Cheapest way to connect every node| I[Minimum Spanning Tree] H -->|Mutually reachable groups in a digraph| J[Strongly Connected Components] H -->|Single points of failure| K[Articulation Points and Bridges] H -->|Clusters in an undirected graph| M[Connected Components] H -->|Throughput through a capacitated network| L[Maximum Flow]
Algorithm Selection
Shortest Path
| Algorithm | Solves | Time | Constraint |
|---|---|---|---|
| BFS | Reachability, shortest path by edge count | O(V + E) | Unweighted graphs |
| DFS | Traversal, cycle detection, finish-order primitives | O(V + E) | General graphs. Topological order still requires a DAG |
| Dijkstra | Single-source shortest path | O((V + E) log V) | Non-negative weights |
| A* Search | Point-to-point shortest path | O((V + E) log E) with a consistent heuristic and lazy heap. Reopenings make runtime re-expansion-dependent | Non-negative weights. Consistency permits close-once optimality, while an admissible but inconsistent heuristic requires reopenings |
| Greedy Best-First Search | Fast point-to-point path, not necessarily optimal | O((V + E) log E) with a lazy heap | Heuristic only. Sacrifices optimality for speed |
| Bidirectional Search | Point-to-point shortest path | About O(b^(d/2)) rather than O(b^d) in the ideal state-space model | Target known. Backward search must be available |
| Bellman-Ford | Single-source shortest path | O(V·E) | Handles negative edges. Detects reachable negative cycles |
| Floyd-Warshall | All-pairs shortest path | Θ(V³) time, Θ(V²) space | Small or dense graphs. Detects negative cycles |
Structure and Connectivity
| Algorithm | Solves | Time | Constraint |
|---|---|---|---|
| Minimum Spanning Tree | Cheapest edge set connecting all vertices | O(E log V) | Connected, undirected, weighted |
| Topological Sort | Linear order respecting dependencies | O(V + E) | Directed acyclic graph |
| Strongly Connected Components | Maximal mutually-reachable vertex sets | O(V + E) | Directed graphs |
| Connected Components | Maximal connected vertex sets | O(V + E) | Undirected graphs |
| Articulation Points and Bridges | Cut vertices and cut edges | O(V + E) | Undirected graphs |
| Maximum Flow | Max s–t throughput. Min cut | O(V·E²) (Edmonds–Karp) | Capacitated network |
NOTE
Not every graph problem admits a polynomial-time algorithm. Hamiltonian Cycle asks for a cycle that visits every vertex exactly once and is NP-complete. No polynomial-time algorithm is known. Exact methods take exponential time in the worst case.