Floyd Warshall All Pairs Shortest Path in DSA C++

Mental Model

We find the shortest path between every pair of points by checking if going through a middle point is better than going directly.

Analogy: Imagine you want to travel between cities. Sometimes going through a third city is faster than going straight. We check all cities as possible middle stops to find the quickest routes.

Graph with 4 nodes:
  (0)---5--->(1)
   |         /|
  10       3  |
   |       /  |
  (3)<---1---(2)

Dry Run Walkthrough

Input: Graph with 4 nodes and edges: 0->1=5, 0->3=10, 1->2=3, 2->3=1

Goal: Find shortest distances between every pair of nodes

Step 1: Initialize distance matrix with direct edges and 0 for same nodes

[[0,5,∞,10],
 [∞,0,3,∞],
 [∞,∞,0,1],
 [∞,∞,∞,0]]

Why: Start with known distances: direct edges or infinity if no direct path

Step 2: Use node 0 as intermediate: update distances if going through 0 is shorter

[[0,5,∞,10],
 [∞,0,3,∞],
 [∞,∞,0,1],
 [∞,∞,∞,0]]

Why: No shorter paths found through node 0 yet

Step 3: Use node 1 as intermediate: update distance 0->2 via 1 (5+3=8 < ∞)

[[0,5,8,10],
 [∞,0,3,∞],
 [∞,∞,0,1],
 [∞,∞,∞,0]]

Why: Going 0->1->2 is shorter than no direct path

Step 4: Use node 2 as intermediate: update distance 0->3 via 2 (8+1=9 < 10) and 1->3 via 2 (3+1=4 < ∞)

[[0,5,8,9],
 [∞,0,3,4],
 [∞,∞,0,1],
 [∞,∞,∞,0]]

Why: Going 0->1->2->3 and 1->2->3 are shorter than direct or previous paths

Step 5: Use node 3 as intermediate: no shorter paths found

[[0,5,8,9],
 [∞,0,3,4],
 [∞,∞,0,1],
 [∞,∞,∞,0]]

Why: No improvements by going through node 3

Result:

Final shortest path matrix:
[[0,5,8,9],
 [∞,0,3,4],
 [∞,∞,0,1],
 [∞,∞,∞,0]]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

const int INF = 1e9;

void floydWarshall(vector<vector<int>>& dist) {
    int n = dist.size();
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dist[i][k] < INF && dist[k][j] < INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

int main() {
    int n = 4;
    vector<vector<int>> dist(n, vector<int>(n, INF));
    for (int i = 0; i < n; ++i) dist[i][i] = 0;

    dist[0][1] = 5;
    dist[0][3] = 10;
    dist[1][2] = 3;
    dist[2][3] = 1;

    floydWarshall(dist);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dist[i][j] == INF) cout << "INF" << " ";
            else cout << dist[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

for (int k = 0; k < n; ++k) {

select each node as intermediate point

for (int i = 0; i < n; ++i) {

iterate over all start nodes

for (int j = 0; j < n; ++j) {

iterate over all end nodes

if (dist[i][k] < INF && dist[k][j] < INF && dist[i][k] + dist[k][j] < dist[i][j]) {

check if path i->k->j is shorter than current i->j

dist[i][j] = dist[i][k] + dist[k][j];

update shortest distance with new shorter path

Output

0 5 8 9 

INF 0 3 4 

INF INF 0 1 

INF INF INF 0 

Complexity Analysis

Time: O(n^3) because we check every pair of nodes for every possible intermediate node

Space: O(n^2) because we store distances between all pairs in a matrix

vs Alternative: Compared to running Dijkstra from each node (O(n * (E + V log V))), Floyd Warshall is simpler but slower for sparse graphs

Edge Cases

Graph with no edges

Distances remain infinity except zero on diagonals

DSA C++

if (dist[i][k] < INF && dist[k][j] < INF && dist[i][k] + dist[k][j] < dist[i][j]) {

Graph with self loops

Distance from node to itself stays zero or updated if negative cycle

DSA C++

for (int i = 0; i < n; ++i) dist[i][i] = 0;

Graph with negative edges but no negative cycles

Algorithm finds correct shortest paths including negative edges

DSA C++

if (dist[i][k] < INF && dist[k][j] < INF && dist[i][k] + dist[k][j] < dist[i][j]) {

When to Use This Pattern

When asked to find shortest paths between all pairs of points in a graph, especially with negative edges but no negative cycles, use Floyd Warshall because it systematically checks all intermediate nodes.

Common Mistakes

Mistake: Not initializing distance from node to itself as zero
Fix: Set dist[i][i] = 0 for all i before running the algorithm

Mistake: Updating distances without checking if intermediate paths exist (causing overflow)
Fix: Check dist[i][k] and dist[k][j] are not infinity before adding

Summary

Finds shortest paths between every pair of nodes in a graph.

Use when you need all pairs shortest paths, including graphs with negative edges but no negative cycles.

The key is checking if going through each node improves the path between every pair.

Practice

1. What is the main purpose of the Floyd Warshall algorithm in graph theory?

easy

A. To find shortest paths between all pairs of vertices in a weighted graph

B. To find the minimum spanning tree of a graph

C. To detect cycles in a directed graph

D. To perform depth-first search traversal

Solution

1. Step 1: Understand Floyd Warshall algorithm goal

   The Floyd Warshall algorithm is designed to find shortest paths between every pair of vertices in a weighted graph, including negative weights but no negative cycles.

2. Step 2: Compare with other graph algorithms

   Minimum spanning tree algorithms find a tree connecting all vertices with minimum total edge weight, cycle detection algorithms find cycles, and DFS is a traversal method. These are different from Floyd Warshall's goal.

3. Final Answer:

   To find shortest paths between all pairs of vertices in a weighted graph -> Option A

4. Quick Check:

   Floyd Warshall = all pairs shortest paths [OK]

Hint: Floyd Warshall finds shortest paths between all vertex pairs [OK]

Common Mistakes:

• Confusing Floyd Warshall with minimum spanning tree algorithms
• Thinking it only finds shortest path from one source
• Assuming it detects cycles instead of paths

2. Which of the following is the correct way to initialize the distance matrix dist for Floyd Warshall in C++ for a graph with n vertices and adjacency matrix graph?

easy

A. for (int i = 0; i < n; i++) dist[i] = graph[i];

B. for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = graph[i][j];

C. dist = graph;

D. dist = new int[n][n];

Solution

1. Step 1: Understand distance matrix initialization

   We need to copy each element from the adjacency matrix graph to dist element-wise because dist is a 2D array and direct assignment is not allowed in C++.

2. Step 2: Analyze each option

   for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = graph[i][j]; uses nested loops to copy each element correctly. for (int i = 0; i < n; i++) dist[i] = graph[i]; tries to assign a row pointer which is invalid for 2D arrays. dist = graph; tries direct assignment which is invalid for arrays. dist = new int[n][n]; only allocates memory but does not initialize values.

3. Final Answer:

   for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = graph[i][j]; -> Option B

4. Quick Check:

   Element-wise copy needed = for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = graph[i][j]; [OK]

Hint: Use nested loops to copy 2D arrays element-wise [OK]

Common Mistakes:

• Trying to assign 2D arrays directly
• Copying only row pointers instead of elements
• Not initializing distance matrix before algorithm

3. What will be the output distance matrix after running Floyd Warshall on the following graph with 3 vertices and adjacency matrix:

int graph[3][3] = {
  {0, 5, 999},
  {50, 0, 15},
  {30, 999, 0}
};

Assuming 999 represents no direct edge.

medium

A. [[0, 5, 20], [50, 0, 15], [30, 35, 0]]

B. [[0, 5, 999], [50, 0, 15], [30, 999, 0]]

C. [[0, 5, 999], [50, 0, 15], [30, 45, 0]]

D. [[0, 5, 20], [45, 0, 15], [30, 35, 0]]

Solution

1. Step 1: Initialize distance matrix

   Start with dist = graph:
   dist = [[0,5,999],[50,0,15],[30,999,0]]

2. Step 2: Update distances using Floyd Warshall

   Check if going through vertex 0 improves paths:
   dist[1][2] = min(15, dist[1][0]+dist[0][2]) = min(15, 50+999)=15 (no change)
   dist[2][1] = min(999, dist[2][0]+dist[0][1]) = min(999, 30+5)=35 (updated)
   Check through vertex 1:
   dist[0][2] = min(999, dist[0][1]+dist[1][2]) = min(999, 5+15)=20 (updated)
   dist[2][2] = min(0, dist[2][1]+dist[1][2]) = min(0, 35+15)=0 (no change)
   Check through vertex 2:
   dist[1][0] = min(50, dist[1][2]+dist[2][0]) = min(50, 15+30)=45 (updated)

3. Final Answer:

   [[0, 5, 20], [45, 0, 15], [30, 35, 0]] -> Option D

4. Quick Check:

   Updated shortest paths matrix = [[0, 5, 20], [45, 0, 15], [30, 35, 0]] [OK]

Hint: Check all intermediate vertices to update shortest paths [OK]

Common Mistakes:

• Not updating paths through intermediate vertices
• Confusing no edge (999) with zero
• Missing updates for reverse paths

4. Identify the error in this Floyd Warshall code snippet and select the fix:

for (int k = 0; k < n; k++) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (dist[i][k] + dist[k][j] < dist[i][j])
        dist[i][j] = dist[i][k] + dist[k][j];
    }
  }
}

medium

A. Check if dist[i][k] and dist[k][j] are not infinity before adding

B. No error; code is correct

C. Change loop order to i, j, k

D. Use max instead of min in the if condition

Solution

1. Step 1: Understand potential overflow in addition

   If dist[i][k] or dist[k][j] is infinity (representing no path), adding them causes incorrect results or overflow.

2. Step 2: Fix by checking for infinity before addition

   Before adding dist[i][k] + dist[k][j], ensure both are not infinity to avoid invalid updates.

3. Final Answer:

   Check if dist[i][k] and dist[k][j] are not infinity before adding -> Option A

4. Quick Check:

   Prevent invalid addition by checking infinity [OK]

Hint: Always check for infinity before adding distances [OK]

Common Mistakes:

• Ignoring infinity checks causing wrong updates
• Changing loop order incorrectly
• Using max instead of min for shortest path

5. Given a weighted directed graph with 4 vertices and adjacency matrix:

int graph[4][4] = {
  {0, 3, 999, 7},
  {8, 0, 2, 999},
  {5, 999, 0, 1},
  {2, 999, 999, 0}
};

Use Floyd Warshall to find the shortest path distance from vertex 0 to vertex 3 after all updates. What is the shortest distance?

hard

A. 8

B. 7

C. 6

D. 9

Solution

1. Step 1: Initialize distance matrix

   Start with dist = graph:
   dist = [[0,3,999,7],[8,0,2,999],[5,999,0,1],[2,999,999,0]]

2. Step 2: Update distances through intermediate vertices

   Check paths through vertex 0:
   dist[1][3] = min(999, dist[1][0]+dist[0][3]) = min(999, 8+7)=15
   dist[2][1] = min(999, dist[2][0]+dist[0][1]) = min(999, 5+3)=8
   dist[3][1] = min(999, dist[3][0]+dist[0][1]) = min(999, 2+3)=5
   Check paths through vertex 1:
   dist[0][2] = min(999, dist[0][1]+dist[1][2]) = min(999, 3+2)=5
   dist[0][3] = min(7, dist[0][1]+dist[1][3]) = min(7, 3+15)=7
   dist[3][2] = min(999, dist[3][1]+dist[1][2]) = min(999, 5+2)=7
   Check paths through vertex 2:
   dist[1][3] = min(15, dist[1][2]+dist[2][3]) = min(15, 2+1)=3 (updated)
   dist[0][3] = min(7, dist[0][2]+dist[2][3]) = min(7, 5+1)=6 (updated)
   Check paths through vertex 3:
   dist[2][0] = min(5, dist[2][3]+dist[3][0]) = min(5, 1+2)=3 (updated)

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Shortest path 0 to 3 = 6 [OK]

Hint: Update distances through all vertices stepwise [OK]

Common Mistakes:

• Not updating paths through all intermediate vertices
• Missing shorter path updates
• Confusing direct edge with shortest path