Senior LevelData Structures & Algorithms
How does Floyd-Warshall solve All-Pairs Shortest Paths?
❓ Interview Prompt: Explain Floyd-Warshall O(V³) algorithm for all-pairs shortest paths, negative cycle detection, and transitive closure.
Floyd-Warshall computes shortest paths between all pairs of vertices in $O(V^3)$ time.
Key Recurrence:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Iterating intermediate vertex $k$ from $0$ to $V - 1$: for each pair $(i, j)$, check if routing through $k$ improves the path.
Negative Cycle Detection:
If dist[i][i] < 0 after the algorithm → vertex $i$ lies on a negative cycle.
Applications:
•
Network routing (all-to-all latency matrix).
•
Transitive closure (reachability).
•
Detecting arbitrage in currency exchange graphs.
Code Implementation Example
typescript
function floydWarshall(graph: number[][]): number[][] | null {
const n = graph.length;
const dist = graph.map(row => [...row]); // copy adjacency matrix
for (let k = 0; k < n; k++) { // intermediate vertex
for (let i = 0; i < n; i++) { // source
for (let j = 0; j < n; j++) { // destination
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// Negative cycle check
for (let i = 0; i < n; i++)
if (dist[i][i] < 0) return null;
return dist;
}💡Floyd-Warshall O(V³) all-pairs shortest paths with negative cycle detection.
🎯 Interview Key Takeaway
Floyd-Warshall finds all-pairs shortest paths in O(V³). Use it for dense graphs or when you need all-to-all distances. Negative diagonal = negative cycle.
#DSA#Floyd-Warshall#Graph#All-Pairs Shortest Path#Senior
Back to all Data Structures & Algorithms Questions→