Floyd Warshall All Pairs Shortest Path in DSA Python

Mental Model

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

Analogy: Imagine you want to find the quickest way to travel between every pair of cities. Sometimes, stopping at a third city on the way makes the trip faster than going straight.

 0   3  ∞  ∞
 2   0  ∞  ∞
 ∞   7  0   1
 6  ∞  ∞   0

Here, numbers show direct travel times between cities; ∞ means no direct path.

Dry Run Walkthrough

Input: Graph with 4 nodes and edges: 0->1=3, 0->2=∞, 0->3=∞, 1->0=2, 1->2=∞, 1->3=∞, 2->1=7, 2->3=1, 3->0=6

Goal: Find shortest travel times between every pair of cities using Floyd Warshall algorithm

Step 1: Start with initial distances matrix

0 -> 3 -> ∞ -> ∞
2 -> 0 -> ∞ -> ∞
∞ -> 7 -> 0 -> 1
6 -> ∞ -> ∞ -> 0

Why: We need the starting point with direct distances to compare improvements

Step 2: Use node 0 as intermediate to update paths

0 -> 3 -> ∞ -> ∞
2 -> 0 -> ∞ -> ∞
∞ -> 7 -> 0 -> 1
6 -> 9 -> ∞ -> 0

Why: Check if going through node 0 improves any path

Step 3: Use node 1 as intermediate to update paths

0 -> 3 -> ∞ -> ∞
2 -> 0 -> ∞ -> ∞
9 -> 7 -> 0 -> 1
6 -> 9 -> ∞ -> 0

Why: Check if going through node 1 improves any path

Step 4: Use node 2 as intermediate to update paths

0 -> 3 -> ∞ -> ∞
2 -> 0 -> ∞ -> ∞
9 -> 7 -> 0 -> 1
6 -> 9 -> ∞ -> 0

Why: Check if going through node 2 improves any path

Step 5: Use node 3 as intermediate to update paths

0 -> 3 -> ∞ -> ∞
2 -> 0 -> ∞ -> ∞
7 -> 7 -> 0 -> 1
6 -> 9 -> ∞ -> 0

Why: Check if going through node 3 improves any path

Result:

0 -> 3 -> ∞ -> ∞
2 -> 0 -> ∞ -> ∞
7 -> 7 -> 0 -> 1
6 -> 9 -> ∞ -> 0

Annotated Code

DSA Python

INF = float('inf')

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[INF] * vertices for _ in range(vertices)]
        for i in range(vertices):
            self.graph[i][i] = 0

    def floyd_warshall(self):
        dist = [row[:] for row in self.graph]
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        return dist

    def print_solution(self, dist):
        for i in range(self.V):
            for j in range(self.V):
                if dist[i][j] == INF:
                    print('INF', end=' ')
                else:
                    print(dist[i][j], end=' ')
            print()

# Driver code
if __name__ == '__main__':
    g = Graph(4)
    g.graph = [
        [0, 3, INF, INF],
        [2, 0, INF, INF],
        [INF, 7, 0, 1],
        [6, INF, INF, 0]
    ]
    dist = g.floyd_warshall()
    g.print_solution(dist)

dist = [row[:] for row in self.graph]

copy initial distances to dist matrix to update shortest paths

for k in range(self.V):

consider each node k as intermediate point

for i in range(self.V):

for each start node i

for j in range(self.V):

for each end node j

if 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 path distance

Output

0 3 INF INF 

2 0 INF INF 

7 7 0 1 

6 9 INF 0 

Complexity Analysis

Time: O(V^3) because we check all pairs (i, j) for each intermediate node k

Space: O(V^2) to store the distance matrix for all pairs

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

Edge Cases

Graph with no edges except self loops

Distances remain zero on diagonal and infinite elsewhere

DSA Python

for i in range(vertices): self.graph[i][i] = 0

Graph with negative edge weights but no negative cycles

Algorithm correctly finds shortest paths including negative edges

DSA Python

if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j]

Graph with negative cycle

Algorithm does not detect negative cycles; distances may become incorrect

DSA Python

No explicit guard; Floyd Warshall needs extra check for negative cycles

When to Use This Pattern

When asked to find shortest paths between all pairs of points in a graph, especially with possible negative edges, Floyd Warshall is the go-to pattern because it systematically checks all intermediate nodes.

Common Mistakes

Mistake: Not copying the original graph matrix before updating distances, causing incorrect updates
Fix: Create a separate distance matrix copy before starting the updates

Mistake: Forgetting to initialize distance from a node to itself as zero
Fix: Set distance[i][i] = 0 for all nodes i before starting

Mistake: Not checking if the new path through k is shorter before updating
Fix: Always compare dist[i][k] + dist[k][j] with dist[i][j] before assignment

Summary

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

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

The key insight is to improve paths by considering each node as a possible middle stop.

Practice

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

easy

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

B. To find the minimum spanning tree of a graph

C. To perform a depth-first search traversal

D. To detect cycles in a graph

Solution

1. Step 1: Understand Floyd Warshall's goal

   The Floyd Warshall algorithm calculates shortest paths between every pair of vertices in a weighted graph.

2. Step 2: Compare with other graph algorithms

   Minimum spanning tree, DFS, and cycle detection serve different purposes than Floyd Warshall.

3. Final Answer:

   To find the 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 with minimum spanning tree algorithms
• Thinking it finds shortest path from one source only
• Mixing with traversal algorithms like DFS or BFS

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

easy

A. dist = [[0] * n] * n

B. dist = [[float('inf')] * n for _ in range(n)]

C. dist = [float('inf')] * n * n

D. dist = [0 for _ in range(n)]

Solution

1. Step 1: Understand matrix initialization

   We need a 2D list with size n x n, each element set to infinity initially.

2. Step 2: Check each option

   dist = [[float('inf')] * n for _ in range(n)] correctly creates a new list for each row with float('inf'). dist = [float('inf')] * n * n creates a 1D list, not 2D. dist = [[0] * n] * n creates shallow copies causing aliasing. dist = [0 for _ in range(n)] creates 1D list.

3. Final Answer:

   dist = [[float('inf')] * n for _ in range(n)] -> Option B

4. Quick Check:

   2D list with inf values = dist = [[float('inf')] * n for _ in range(n)] [OK]

Hint: Use list comprehension for 2D matrix initialization [OK]

Common Mistakes:

• Using multiplication for 2D lists causing shared references
• Creating 1D list instead of 2D
• Initializing with zeros instead of infinity

3. What will be the output distance matrix after running Floyd Warshall on this graph represented by adjacency matrix?

graph = [
  [0, 3, float('inf'), 7],
  [8, 0, 2, float('inf')],
  [5, float('inf'), 0, 1],
  [2, float('inf'), float('inf'), 0]
]

medium

A. [[0, 3, 5, 6], [5, 0, 2, 3], [3, 6, 0, 1], [2, 5, 7, 0]]

B. [[0, 3, 10, 7], [8, 0, 2, 3], [5, 8, 0, 1], [2, 5, 7, 0]]

C. [[0, 3, 7, 7], [8, 0, 2, 3], [5, 8, 0, 1], [2, 5, 7, 0]]

D. [[0, 3, 5, 7], [8, 0, 2, 3], [5, 8, 0, 1], [2, 5, 7, 0]]

Solution

1. Step 1: Initialize dist matrix same as graph

   Start with dist = graph matrix, where float('inf') means no direct edge.

2. Step 2: Update distances using Floyd Warshall logic

   Iterate k from 0 to 3, update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for all i,j. After all iterations, shortest paths are computed.

3. Final Answer:

   [[0, 3, 5, 6], [5, 0, 2, 3], [3, 6, 0, 1], [2, 5, 7, 0]] -> Option A

4. Quick Check:

   All pairs shortest paths matrix = [[0, 3, 5, 6], [5, 0, 2, 3], [3, 6, 0, 1], [2, 5, 7, 0]] [OK]

Hint: Update dist with min of current and via intermediate vertex [OK]

Common Mistakes:

• Not updating distances through intermediate vertices
• Confusing indices in nested loops
• Leaving float('inf') where shorter paths exist

4. Consider this snippet of Floyd Warshall implementation in Python:

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

What is the main bug if dist[i][k] or dist[k][j] is float('inf')?

medium

A. It causes incorrect updates because adding infinity is not handled

B. It causes incorrect addition leading to overflow errors

C. No bug, the code works fine with infinity values

D. It causes syntax errors due to float('inf') usage

Solution

1. Step 1: Understand addition with infinity in Python

   float('inf') + any finite number = float('inf'), and float('inf') + float('inf') = float('inf').

2. Step 2: Check the condition

   The condition if dist[i][k] + dist[k][j] < dist[i][j] will be False whenever the sum is inf, because inf is not less than any finite or inf value. Thus, no incorrect updates occur; invalid paths are correctly skipped.

3. Final Answer:

   No bug, the code works fine with infinity values -> Option C

4. Quick Check:

   inf + x = inf, inf < y always False for path updates [OK]

Hint: Python's float('inf') handles additions and comparisons correctly for FW [OK]

Common Mistakes:

• Believing inf causes incorrect updates
• Confusing with integer overflow issues
• Thinking syntax error with inf

5. Given a graph with negative edge weights but no negative cycles, how does Floyd Warshall algorithm handle these edges to find shortest paths?

hard

A. It requires a separate algorithm to preprocess negative edges before running

B. It fails because it cannot handle negative weights at all

C. It ignores negative edges and only uses positive weights

D. It updates distances by considering intermediate vertices, correctly handling negative edges without cycles

Solution

1. Step 1: Understand Floyd Warshall with negative edges

   The algorithm can handle negative edges by updating distances through intermediate vertices, as long as no negative cycles exist.

2. Step 2: Confirm no negative cycle condition

   If negative cycles exist, shortest paths are undefined. Without them, Floyd Warshall converges to correct shortest paths.

3. Final Answer:

   It updates distances by considering intermediate vertices, correctly handling negative edges without cycles -> Option D

4. Quick Check:

   Negative edges allowed if no negative cycles [OK]

Hint: Floyd Warshall handles negative edges if no negative cycles exist [OK]

Common Mistakes:

• Thinking Floyd Warshall cannot handle any negative edges
• Confusing negative edges with negative cycles
• Assuming preprocessing is always needed