Faangprep Logo
LoginRegister
Browse Curriculum

Floyd-Warshall Algorithm

Find shortest paths between all pairs of nodes in a weighted graph, handling negative edge weights (but not negative cycles).

510310123
Distance Matrix
0
1
2
3
0
0
5
∞
10
1
∞
0
3
∞
2
∞
∞
0
1
3
∞
∞
∞
0

Ready to start

Speed
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

Intuition

Imagine you have a map of cities. You want to know the shortest path between ANY two cities. Floyd-Warshall checks every possible "stopover" city (k) for every pair of cities (i, j). If going from i to j via k is faster than the current best way, it updates the map.

Concept

All-Pairs Shortest Path: Unlike Dijkstra (one-to-all), this computes the shortest path between every pair of vertices.

Dynamic Programming: It builds the solution incrementally by considering more intermediate nodes allowed in the path.

Relaxation Formula: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

How it Works

The algorithm uses three nested loops:

  1. k (Intermediate): Iterate through each node as a potential pivot.
  2. i (Source): Iterate through each node as a starting point.
  3. j (Destination): Iterate through each node as a destination.
  4. Check if path i -> k -> j is strictly improved.
  5. Update the distance matrix if a shorter path is found.

Step-by-Step Breakdown

Watch the Matrix and Graph:

  • Matrix Cell: Represents the current shortest distance between row (i) and column (j).
  • Light Orange Node (k): The current intermediate pivot being tested.
  • Emerald Highlight: A successful update where a shorter path was found.

When to Use

Applications:

  • Finding optimal paths between all pairs of locations (e.g., flight routing).
  • Transitive closure (determining reachability).
  • Dense graphs where edge count is high.

When NOT to Use

  • Large Graphs: O(V³) complexity makes it too slow for V > 400-500.
  • Single-Source only needed: Use Dijkstra or Bellman-Ford if you only need paths from one specific start node.

How to Identify

"Find shortest paths between every pair of nodes", "Transitive closure", "Dense graph all-pairs".

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep