Floyd Warshall All Pairs Shortest Path in DSA Go

Mental Model

We find the shortest paths between all pairs of points by checking if going through a middle point makes the path shorter.

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

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

Distance matrix before:
[0, 5, ∞, 10]
[∞, 0, 3, ∞]
[∞, ∞, 0, 1]
[∞, ∞, ∞, 0]

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: We start with known direct distances or infinity if no direct edge

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 at this step

Step 3: Use node 1 as intermediate: update distance from 0 to 2 via 1

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

Why: 0->1 + 1->2 = 5 + 3 = 8 is shorter than ∞, so update

Step 4: Use node 2 as intermediate: update distance from 0 to 3 via 2

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

Why: 0->2 + 2->3 = 8 + 1 = 9 is shorter than 10, update 0->3; also 1->2 + 2->3 = 3 + 1 = 4 update 1->3

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

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

Why: No paths improve by going through node 3

Result:

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

Annotated Code

DSA Go

package main

import (
	"fmt"
	"math"
)

func floydWarshall(graph [][]int) [][]int {
	n := len(graph)
	// Initialize distance matrix
	dist := make([][]int, n)
	for i := 0; i < n; i++ {
		dist[i] = make([]int, n)
		for j := 0; j < n; j++ {
			if i == j {
				dist[i][j] = 0
			} else if graph[i][j] != 0 {
				dist[i][j] = graph[i][j]
			} else {
				dist[i][j] = math.MaxInt32
			}
		}
	}

	// Update distances using each node as intermediate
	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				// Check if path i->k + k->j is shorter than i->j
				if dist[i][k] != math.MaxInt32 && dist[k][j] != math.MaxInt32 && dist[i][k]+dist[k][j] < dist[i][j] {
					dist[i][j] = dist[i][k] + dist[k][j]
				}
			}
		}
	}

	return dist
}

func printMatrix(dist [][]int) {
	n := len(dist)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if dist[i][j] == math.MaxInt32 {
				fmt.Print("∞ ")
			} else {
				fmt.Printf("%d ", dist[i][j])
			}
		}
		fmt.Println()
	}
}

func main() {
	graph := [][]int{
		{0, 5, 0, 10},
		{0, 0, 3, 0},
		{0, 0, 0, 1},
		{0, 0, 0, 0},
	}
	distance := floydWarshall(graph)
	printMatrix(distance)
}

for i := 0; i < n; i++ { for j := 0; j < n; j++ { if i == j { dist[i][j] = 0 } else if graph[i][j] != 0 { dist[i][j] = graph[i][j] } else { dist[i][j] = math.MaxInt32 } } }

Initialize distance matrix with direct edges or infinity, zero for same node

for k := 0; k < n; k++ { for i := 0; i < n; i++ { for j := 0; j < n; j++ { if dist[i][k] != math.MaxInt32 && dist[k][j] != math.MaxInt32 && dist[i][k]+dist[k][j] < dist[i][j] { dist[i][j] = dist[i][k] + dist[k][j] } } } }

Check if path through k is shorter and update distance

Output

0 5 8 9 

∞ 0 3 4 

∞ ∞ 0 1 

∞ ∞ ∞ 0 

Complexity Analysis

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

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 and works well for dense graphs but slower for sparse large graphs

Edge Cases

Graph with no edges

Distances remain infinity except zero on diagonal

DSA Go

if i == j {
	dist[i][j] = 0
} else if graph[i][j] != 0 {
	dist[i][j] = graph[i][j]
} else {
	dist[i][j] = math.MaxInt32
}

Graph with self loops

Distance to self is zero, self loops with positive weight ignored as shorter path is zero

DSA Go

if i == j {
	dist[i][j] = 0
}

Graph with negative edges but no negative cycles

Algorithm correctly finds shortest paths including negative edges

DSA Go

if dist[i][k] != math.MaxInt32 && dist[k][j] != math.MaxInt32 && dist[i][k]+dist[k][j] < dist[i][j] {
	dist[i][j] = dist[i][k] + dist[k][j]
}

When to Use This Pattern

When you need shortest paths between all pairs of points and the graph can have negative edges but no negative cycles, use Floyd Warshall because it systematically checks all intermediate nodes.

Common Mistakes

Mistake: Not initializing distances correctly, especially forgetting to set zero for same node pairs
Fix: Explicitly set distance[i][i] = 0 for all i before starting updates

Mistake: Updating distances without checking if intermediate distances are infinity, causing integer 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 and graph may have negative edges but no negative cycles.

The key insight is checking if going through each node as an intermediate point shortens the path.

Practice

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

easy

A. To perform a depth-first search traversal

B. To find the minimum spanning tree of a graph

C. To detect cycles in a graph

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

Solution

1. Step 1: Understand Floyd Warshall's 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 subset of edges connecting all vertices with minimum total weight, cycle detection finds cycles, and DFS is a traversal method. These are different from Floyd Warshall's all pairs shortest path goal.

3. Final Answer:

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

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
• Mixing it with traversal algorithms like DFS

2. Which of the following is the correct way to initialize the distance matrix dist for Floyd Warshall in Go, given graph as adjacency matrix and V as number of vertices?

easy

A. dist = graph

B. for i := 0; i < V; i++ { dist[i] = graph[i] }

C. for i := 0; i < V; i++ { for j := 0; j < V; j++ { dist[i][j] = graph[i][j] } }

D. dist := make([]int, V*V)

Solution

1. Step 1: Understand matrix copying in Go

   In Go, to copy a 2D slice (matrix), you must copy each element individually. Assigning one slice to another copies the reference, not the data.

2. Step 2: Analyze options

   for i := 0; i < V; i++ { for j := 0; j < V; j++ { dist[i][j] = graph[i][j] } } copies each element explicitly, correctly initializing dist. for i := 0; i < V; i++ { dist[i] = graph[i] } copies slice references, not elements. dist = graph assigns reference, not copy. dist := make([]int, V*V) creates a 1D slice, not a 2D matrix.

3. Final Answer:

   for i := 0; i < V; i++ { for j := 0; j < V; j++ { dist[i][j] = graph[i][j] } } -> Option C

4. Quick Check:

   Copy element-wise for matrix copy [OK]

Hint: Copy 2D slices element-wise to avoid reference issues [OK]

Common Mistakes:

• Assigning slices directly causing shared references
• Using 1D slice instead of 2D for matrix
• Not initializing inner slices before assignment
• Assuming slice assignment copies data

3. What will be the output distance matrix after running Floyd Warshall on the following graph represented as adjacency matrix (9999 means no direct edge):

graph := [][]int{
  {0, 3, 9999, 7},
  {8, 0, 2, 9999},
  {5, 9999, 0, 1},
  {2, 9999, 9999, 0},
}

medium

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

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

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

D. [[0, 3, 4, 6], [7, 0, 2, 3], [3, 6, 0, 1], [2, 5, 7, 0]]

Solution

1. Step 1: Initialize distance matrix

   Start with given graph matrix where 9999 means no direct edge. Distances on diagonal are 0.

2. Step 2: Apply Floyd Warshall updates

   Check all triples (i, j, k) and update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After iterations, shortest paths are:
   dist[0][2] = min(9999, 3+2) = 5
   dist[0][3] = min(7, 3+2+1) = 6
   dist[1][0] = min(8, 2+1+2) = 7
   dist[1][3] = min(9999, 2+1) = 3
   dist[2][0] = min(5, 1+2) = 3
   dist[2][1] = min(9999, 1+2+3) = 6
   dist[3][1] = min(9999, 2+3) = 5
   dist[3][2] = min(9999, 2+3+2) = 7

3. Final Answer:

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

4. Quick Check:

   Floyd Warshall updates shortest paths correctly [OK]

Hint: Update dist[i][j] using intermediate k for all triples [OK]

Common Mistakes:

• Not updating paths through intermediate vertices
• Confusing no edge (9999) with zero
• Forgetting to update all pairs in nested loops
• Incorrectly summing distances

4. Consider this Go code snippet for Floyd Warshall. What is the bug causing incorrect shortest path results?

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

medium

A. Missing check for dist[i][k] or dist[k][j] being infinity before addition

B. No bug; code is correct

C. Loop order should be i, j, k instead of k, i, j

D. Should use <= instead of < in if condition

Solution

1. Step 1: Understand the addition of distances

   When dist[i][k] or dist[k][j] is infinity (e.g., 9999), adding them can cause integer overflow or incorrect comparisons.

2. Step 2: Identify missing checks

   The code does not check if dist[i][k] or dist[k][j] is infinity before adding. This can cause wrong updates to dist[i][j]. Proper code should skip addition if either is infinity.

3. Final Answer:

   Missing check for dist[i][k] or dist[k][j] being infinity before addition -> Option A

4. Quick Check:

   Check infinity before adding distances [OK]

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

Common Mistakes:

• Ignoring infinity checks causing wrong updates
• Changing loop order unnecessarily
• Using <= instead of < does not fix logic
• Assuming code is correct without boundary checks

5. Given a graph with vertices representing cities and edges representing travel times, how can Floyd Warshall be adapted to also reconstruct the shortest path between any two cities?

hard

A. Store all paths explicitly in a list during the algorithm

B. Maintain a separate predecessor matrix updated during relaxation to track paths

C. Run Dijkstra's algorithm for each city instead

D. Use BFS instead of Floyd Warshall for path reconstruction

Solution

1. Step 1: Understand Floyd Warshall's limitation

   Floyd Warshall computes shortest distances but does not store path details by default.

2. Step 2: Use predecessor matrix for path reconstruction

   By maintaining a predecessor matrix where predecessor[i][j] stores the vertex before j on the shortest path from i, we can reconstruct the path after the algorithm finishes.

3. Step 3: Other options analysis

   Storing all paths explicitly is inefficient. Running Dijkstra repeatedly is possible but less efficient for dense graphs. BFS is not suitable for weighted graphs.

4. Final Answer:

   Maintain a separate predecessor matrix updated during relaxation to track paths -> Option B

5. Quick Check:

   Predecessor matrix enables path reconstruction [OK]

Hint: Use predecessor matrix to rebuild shortest paths [OK]

Common Mistakes:

• Not tracking predecessors, so no path info
• Trying to store all paths explicitly causing inefficiency
• Confusing BFS with weighted shortest path algorithms
• Using Dijkstra repeatedly instead of Floyd Warshall