Bellman-Ford Algorithm
Finds shortest paths from a source to all nodes, handling negative edge weights. Algorithm: initialize dist[source]=0, dist[all others]=inf. Repeat V-1 times: for each edge (u, v, w): if dist[u] + w < dist[v]: dist[v] = dist[u] + w (relax edge). After V-1 iterations, all shortest paths are found (longest shortest path uses at most V-1 edges). Negative cycle detection: run one more iteration. If any dist can still be reduced: a negative cycle exists (report it). Time: O(VE) — slower than Dijkstra's O((V+E) log V) but handles negative weights. Use Bellman-Ford for: graphs with negative edges, detecting negative cycles, as a subroutine in Johnson's algorithm (all-pairs shortest paths).
Floyd-Warshall Algorithm
Finds shortest paths between all pairs of nodes (all-pairs shortest paths, APSP). dp[i][j] = shortest distance from i to j. Initialize: dp[i][i]=0, dp[i][j]=edge weight if edge exists, else infinity. Triple nested loop: for k in 0..V: for i in 0..V: for j in 0..V: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]). Interpretation: after iteration k, dp[i][j] = shortest path from i to j using only intermediate nodes 0..k. Time: O(V^3). Space: O(V^2). Use for: dense graphs where you need all-pairs distances, small graphs (V <= 1000), detecting negative cycles (if dp[i][i] < 0 for any i after the algorithm, there is a negative cycle reachable from i).
Minimum Spanning Tree: Kruskal’s Algorithm
A Minimum Spanning Tree (MST) connects all V nodes with V-1 edges of minimum total weight. Kruskal’s: sort all edges by weight. Use Union-Find to track connected components. For each edge in sorted order: if the edge connects two different components (find(u) != find(v)): add to MST, union(u, v). Stop when MST has V-1 edges. Time: O(E log E) for sorting, O(E alpha(V)) for Union-Find operations. Prim’s algorithm alternative: starts from one node, greedily adds the cheapest edge connecting the MST to a new node. Uses a min-heap. Time: O((V+E) log V). Prefer Kruskal’s for sparse graphs (fewer edges to sort); Prim’s for dense graphs (more edges, heap is more efficient).
Tarjan’s Strongly Connected Components
A Strongly Connected Component (SCC) is a maximal set of nodes where every node is reachable from every other. Tarjan’s algorithm finds all SCCs in O(V+E) using DFS. Key concepts: discovery time (disc[v], DFS order), low value (low[v], the lowest disc reachable from v’s subtree via back edges), stack (tracks the current DFS path). DFS: when visiting v: set disc[v]=low[v]=timer++, push v onto stack. For each neighbor u: if unvisited: recurse, then low[v] = min(low[v], low[u]). If u is on the stack: low[v] = min(low[v], disc[u]) (back edge). SCC root: if low[v] == disc[v], v is the root of an SCC. Pop from stack until v is popped — all popped nodes form the SCC. Applications: finding circular dependencies, 2-SAT problem, condensation graph.
Eulerian Path and Circuit
An Eulerian path visits every edge exactly once. An Eulerian circuit visits every edge exactly once and returns to the start. Conditions for undirected graph: Eulerian circuit exists if all vertices have even degree and the graph is connected. Eulerian path (not circuit) exists if exactly 2 vertices have odd degree. Hierholzer’s algorithm finds the Eulerian circuit in O(E): start at any vertex (or one with odd degree for a path). DFS using a stack: while the current vertex has unvisited edges, traverse an edge, remove it (avoid re-traversal). When stuck (no unvisited edges): add to circuit. Backtrack. Common application: “Reconstruct Itinerary” (LeetCode 332) — an Eulerian path problem on a directed graph.
Interview Tips
- Bellman-Ford vs Dijkstra: the key differentiator is negative edges. If the graph has negative weights, Dijkstra is incorrect. Use Bellman-Ford or SPFA (Shortest Path Faster Algorithm, an optimization of Bellman-Ford).
- Floyd-Warshall for V=1000 requires 10^9 operations and 8MB for the distance matrix — feasible. For V=10000: 10^12 operations — not feasible.
- Tarjan’s SCC is subtle — the low-link value and stack membership together define an SCC root. Kosaraju’s algorithm (two-pass DFS) is an easier-to-code alternative with the same complexity.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Coinbase Interview Guide