Floyd Warshall All Pairs Shortest Path in DSA C++ - Build from Scratch

Floyd Warshall All Pairs Shortest Path

📖 Scenario: You are working as a city planner. You have a map of cities connected by roads with distances. You want to find the shortest distance between every pair of cities to plan efficient travel routes.

🎯 Goal: Build a program using the Floyd Warshall algorithm to find the shortest distances between all pairs of cities.

📋 What You'll Learn

Create a 2D vector called dist representing the distance matrix between cities

Add a variable V for the number of cities

Implement the Floyd Warshall algorithm using three nested for loops with variables k, i, and j

Print the final shortest distance matrix after applying the algorithm

💡 Why This Matters

🌍 Real World

City planners and map services use shortest path algorithms to find the best routes between locations.

💼 Career

Understanding Floyd Warshall helps in roles involving route optimization, network analysis, and graph algorithms.

1

Create the distance matrix

Create an integer variable V and set it to 4. Then create a 2D vector of integers called dist with these exact values: {{0, 5, 999, 10}, {999, 0, 3, 999}, {999, 999, 0, 1}, {999, 999, 999, 0}}.

DSA C++

int V = 0;
// Your code here

Hint

Use int V = 4; to set the number of cities. Use std::vector> dist = { ... }; to create the matrix.

2

Set the number of vertices

Create an integer variable called V and set it to 4 if not already done. This variable represents the number of cities.

DSA C++

int V = 4;
std::vector> dist = {
    {0, 5, 999, 10},
    {999, 0, 3, 999},
    {999, 999, 0, 1},
    {999, 999, 999, 0}
};
// Your code here

Hint

Make sure the variable V is set to 4 to represent the number of cities.

3

Implement the Floyd Warshall algorithm

Use three nested for loops with variables k, i, and j each running from 0 to V-1. Inside the innermost loop, update dist[i][j] to the minimum of dist[i][j] and dist[i][k] + dist[k][j].

DSA C++

int V = 4;
std::vector> dist = {
    {0, 5, 999, 10},
    {999, 0, 3, 999},
    {999, 999, 0, 1},
    {999, 999, 999, 0}
};

// Your code here

Hint

Use three nested loops with k, i, and j. Update dist[i][j] if a shorter path is found through k.

4

Print the shortest distance matrix

Use two nested for loops with variables i and j each running from 0 to V-1. Inside the inner loop, print dist[i][j] followed by a space. After the inner loop, print a newline.

DSA C++

int V = 4;
std::vector> dist = {
    {0, 5, 999, 10},
    {999, 0, 3, 999},
    {999, 999, 0, 1},
    {999, 999, 999, 0}
};

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

// Your code here

Hint

Print the matrix row by row. Use std::cout << dist[i][j] << " " inside the inner loop and std::cout << std::endl; after the inner loop.

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