1/34
Looks like no tags are added yet.
Minimum hops (unweighted edges)
Breadth-First Search (BFS)
Cheapest path with non-negative edge weights
Dijkstra's Algorithm
Cheapest path with arbitrary edge weights (including negative weights)
Bellman-Ford Algorithm
All-pairs shortest paths
Floyd-Warshall Algorithm
Maximum total throughput from s→t
Ford-Fulkerson or Edmonds-Karp Algorithm
Connect all nodes with the minimum total cost
Kruskal's or Prim's Algorithm (Minimum Spanning Tree)
Maximize the bottleneck capacity on a single path
Maximum Spanning Tree + Breadth-First Search (BFS)
Order items or tasks by dependencies
Topological Sort
Find mutual reachability groups in a directed graph
Strongly Connected Components (SCC)
Detect whether a cycle exists in a graph
Depth-First Search (DFS) checking for back edges
Identify connected components or groups in an undirected graph
Depth-First Search (DFS) or Breadth-First Search (BFS)
Detect the presence of any negative cycle
Bellman-Ford or Floyd-Warshall Algorithm
Minimum number of hops / edges between two nodes — no weights
Breadth-First Search
Shortest weighted path — all edge weights are positive or zero
Dijkstra's Algorithm
Shortest weighted path — some edge weights may be negative
Bellman-Ford
Shortest path between EVERY pair of nodes (all-pairs)
Floyd-Warshall
Can node A reach node B? Is any path possible?
Breadth-First Search
Find all connected components — how many groups of connected nodes?
Depth-First Search (on undirected graph)
SCC (Directed Graph)
Find groups where EVERY node can reach every other node — directed graph
SCC
Does this directed graph have a cycle? Is it a valid DAG?
Depth-First Search
Order tasks so that all dependencies come first (scheduling / prerequisites)
Topological Sort
Find the longest/shortest path through a DAG
Topological Sort combined with Dynamic Programming
Maximize total flow from source s to sink t — integer edge capacities
Ford-Fulkerson
Maximize total flow from source s to sink t — any capacities or large values
Edmonds-Karp
Maximum bipartite matching — pair up two groups optimally
Edmonds-Karp (after building a flow network from the bipartite graph)
Find all maximal groups of mutual reachability in a directed graph
Strongly Connected Components
Simplify a directed cyclic graph into a DAG for further algorithm application
Strongly Connected Components
Find the source SCC — the group that can reach all other SCCs
Strongly Connected Components
Find the sink SCC — the group that no edge leaves
Strongly Connected Components
Detect if a negative cycle exists reachable from a specific source s
Bellman-Ford
Detect if ANY negative cycle exists anywhere in the entire graph
Floyd-Warshall
Widest single path from s to t — maximize the minimum edge weight along the route
Kruskal's Algorithm (with negated weights) followed by Breadth-First Search
Shortest path in a DAG — can handle any edge weights including negative
Topological Sort followed by edge relaxation in topological order
Shortest distance from ANY one of multiple source nodes to all other nodes
Dijkstra's Algorithm or Breadth-First Search with a virtual super-source node
Apply a DAG algorithm to a graph that has cycles
Strongly Connected Components followed by the DAG algorithm on the metagraph