# Advanced Graph Algorithms Interview Patterns: Bellman-Ford, Floyd-Warshall, Kruskal MST, Tarjan SCC (2025)

Source: https://www.techinterview.org/post/3233465014/advanced-graph-algorithms-interview-patterns/
Updated: 2026-04-17 · techinterview.org

## 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](https://techinterview.org/meta-interview/)

Asked at: [Apple Interview Guide](https://techinterview.org/apple-interview/)

Asked at: [LinkedIn Interview Guide](https://techinterview.org/linkedin-interview/)

Asked at: [Coinbase Interview Guide](https://techinterview.org/coinbase-interview/)