Introduction

Floyd Warshall Algorithm is used to find the shortest distance between every pair of vertices in a graph.

You are given:

  • Weighted graph
  • Adjacency matrix

Goal:

Find shortest paths between all pairs of nodes.

Unlike Dijkstra and Bellman Ford, Floyd Warshall computes all-pairs shortest paths in a single execution.

Example

Input

Graph Matrix
0   3   INF  7
8   0   2    INF
5   INF 0    1
2   INF INF  0

Output

0 3 5 65 0 2 3
3 6 0 1
2 5 7 0

Key Observation

For every pair of nodes (i,j), check whether passing through an intermediate node k produces a shorter path.

Algorithm

  1. Initialize distance matrix.
  2. Choose every node as an intermediate node.
  3. Update shortest paths through that node.
  4. Repeat for all vertices.
  5. Final matrix contains shortest distances between all pairs.

Dry Run

Initial Matrix

0   3   INF  7
8   0   2    INF
5   INF 0    1
2   INF INF  0

Using Node 0

Update paths passing through 0

Using Node 1

Update paths passing through 1

Using Node 2

Update paths passing through 2

Using Node 3

Update paths passing through 3


Final Matrix

0 3 5 65 0 2 3
3 6 0 1
2 5 7 0

Approach : Dynamic Programming

For every pair (i,j), try every possible intermediate node k.

If:

dist[i][k] + dist[k][j] < dist[i][j]

then update the shortest distance.

Practice

Complexity Analysis

Time Complexity: O(V³)
Explanation: Three nested loops iterate through all vertices. Every pair of nodes is checked using every possible intermediate node.

Space Complexity: O(V²)
Explanation: A V × V distance matrix is maintained to store shortest path information.

Why This Problem is Important

Floyd Warshall is the standard algorithm for solving All-Pairs Shortest Path problems and is frequently used in graph theory and network routing.

Common Beginner Mistakes

  • Forgetting the third loop for intermediate nodes.
  • Incorrect INF initialization.
  • Updating the original matrix incorrectly.
  • Using Floyd Warshall on very large graphs.

Interview Tip

Always mention:

Floyd Warshall uses Dynamic Programming and checks whether every node can act as an intermediate vertex to improve shortest paths.

Related Questions

  • Bellman Ford Algorithm
  • Dijkstra Algorithm
  • Network Delay Time
  • Find the City With the Smallest Number of Neighbors
  • Cheapest Flights Within K Stops

Final Takeaway

Floyd Warshall is the classic All-Pairs Shortest Path algorithm. It uses Dynamic Programming to compute shortest paths between every pair of vertices and is especially useful when shortest path queries are required for all nodes in the graph.