Shortest Path - Floyd-Warshall
Learn Shortest Path - Floyd-Warshall (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Floyd-Warshall: All-Pairs Shortest Paths Floyd-Warshall finds the shortest distance between every pair of vertices at once. It tries each vertex k as an intermediate stop: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) . Three nested loops give O(V³) time and O(V²) space, which suits small dense graphs. It works with negative edges (but not negative cycles). The outer loop must be over k .
More lessons in Graphs
- Graph Representation - Adjacency Matrix
- Graph Representation - Adjacency List
- Directed Graph
- Undirected Graph
- Weighted Graph
- BFS
- DFS
- Connected Components
- Cycle Detection
- Bipartite Graph
- Topological Sort
- Kahn's Algorithm
- DFS Topological Sort
- Shortest Path - BFS
- Shortest Path - Dijkstra
- Shortest Path - Bellman-Ford
- Minimum Spanning Tree - Prim's
- Minimum Spanning Tree - Kruskal's
- Disjoint Set Union - DSU
- Union-Find
- Strongly Connected Components - Kosaraju
- Strongly Connected Components - Tarjan
- Bridges
- Articulation Points
- Euler Path / Circuit
- Hamiltonian Path / Cycle
- Graph Coloring
- Network Flow
- Maximum Flow
- Bipartite Matching