Floyd Warshall All Pairs Shortest Path in DSA Javascript - Execution Trace

Concept Flow - Floyd Warshall All Pairs Shortest Path

Start with distance matrix

↓

Pick intermediate node k

↓

For each pair (i, j)

↓

Check if path i->k->j is shorter

Yes/No↓

Update dist[i

↓

Repeat for all i, j

↓

Repeat for all k

↓

Final shortest paths matrix

The algorithm updates shortest paths by considering each node as an intermediate point, checking if going through it shortens paths between all pairs.

Execution Sample

DSA Javascript

const dist = [
  [0, 3, Infinity, 7],
  [8, 0, 2, Infinity],
  [5, Infinity, 0, 1],
  [2, Infinity, Infinity, 0]
];
// Floyd Warshall updates dist matrix

This code runs Floyd Warshall on a 4-node graph with initial distances, updating to shortest paths.

Execution Table

Step	Operation	Intermediate k	Pair (i,j)	Old dist[i][j]	New dist[i][j]	Updated?	Matrix State
1	Initialize	-	-	-	-	No	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]
2	k=0, i=0, j=0	0	(0,0)	0	0	No	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]
3	k=0, i=0, j=1	0	(0,1)	3	3	No	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]
4	k=0, i=0, j=2	0	(0,2)	∞	∞	No	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]
5	k=0, i=0, j=3	0	(0,3)	7	7	No	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]
6	k=0, i=1, j=0	0	(1,0)	8	8	No	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]
7	k=0, i=1, j=1	0	(1,1)	0	0	No	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]
8	k=0, i=1, j=2	0	(1,2)	2	2	No	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]
9	k=0, i=1, j=3	0	(1,3)	∞	15	Yes	[[0,3,∞,7],[8,0,2,15],[5,∞,0,1],[2,∞,∞,0]]
10	k=0, i=2, j=0	0	(2,0)	5	5	No	[[0,3,∞,7],[8,0,2,15],[5,∞,0,1],[2,∞,∞,0]]
11	k=0, i=2, j=1	0	(2,1)	∞	8	Yes	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,∞,∞,0]]
12	k=0, i=2, j=2	0	(2,2)	0	0	No	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,∞,∞,0]]
13	k=0, i=2, j=3	0	(2,3)	1	1	No	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,∞,∞,0]]
14	k=0, i=3, j=0	0	(3,0)	2	2	No	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,∞,∞,0]]
15	k=0, i=3, j=1	0	(3,1)	∞	5	Yes	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
16	k=0, i=3, j=2	0	(3,2)	∞	∞	No	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
17	k=0, i=3, j=3	0	(3,3)	0	0	No	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
18	k=1, i=0, j=0	1	(0,0)	0	0	No	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
19	k=1, i=0, j=1	1	(0,1)	3	3	No	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
20	k=1, i=0, j=2	1	(0,2)	∞	5	Yes	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
21	k=1, i=0, j=3	1	(0,3)	7	7	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
22	k=1, i=1, j=0	1	(1,0)	8	8	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
23	k=1, i=1, j=1	1	(1,1)	0	0	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
24	k=1, i=1, j=2	1	(1,2)	2	2	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
25	k=1, i=1, j=3	1	(1,3)	15	17	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
26	k=1, i=2, j=0	1	(2,0)	5	13	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
27	k=1, i=2, j=1	1	(2,1)	8	8	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
28	k=1, i=2, j=2	1	(2,2)	0	0	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
29	k=1, i=2, j=3	1	(2,3)	1	1	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
30	k=1, i=3, j=0	1	(3,0)	2	7	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
31	k=1, i=3, j=1	1	(3,1)	5	5	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
32	k=1, i=3, j=2	1	(3,2)	∞	7	Yes	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,7,0]]
33	k=1, i=3, j=3	1	(3,3)	0	0	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,7,0]]
34	k=2, i=0, j=0	2	(0,0)	0	0	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,7,0]]
35	k=2, i=0, j=1	2	(0,1)	3	3	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,7,0]]
36	k=2, i=0, j=2	2	(0,2)	5	5	No	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,7,0]]
37	k=2, i=0, j=3	2	(0,3)	7	6	Yes	[[0,3,5,6],[8,0,2,15],[5,8,0,1],[2,5,7,0]]
38	k=2, i=1, j=0	2	(1,0)	8	8	No	[[0,3,5,6],[8,0,2,15],[5,8,0,1],[2,5,7,0]]
39	k=2, i=1, j=1	2	(1,1)	0	0	No	[[0,3,5,6],[8,0,2,15],[5,8,0,1],[2,5,7,0]]
40	k=2, i=1, j=2	2	(1,2)	2	2	No	[[0,3,5,6],[8,0,2,15],[5,8,0,1],[2,5,7,0]]
41	k=2, i=1, j=3	2	(1,3)	15	3	Yes	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
42	k=2, i=2, j=0	2	(2,0)	5	5	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
43	k=2, i=2, j=1	2	(2,1)	8	8	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
44	k=2, i=2, j=2	2	(2,2)	0	0	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
45	k=2, i=2, j=3	2	(2,3)	1	1	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
46	k=2, i=3, j=0	2	(3,0)	2	2	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
47	k=2, i=3, j=1	2	(3,1)	5	5	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
48	k=2, i=3, j=2	2	(3,2)	7	7	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
49	k=2, i=3, j=3	2	(3,3)	0	0	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
50	k=3, i=0, j=0	3	(0,0)	0	0	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
51	k=3, i=0, j=1	3	(0,1)	3	3	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
52	k=3, i=0, j=2	3	(0,2)	5	6	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
53	k=3, i=0, j=3	3	(0,3)	6	6	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
54	k=3, i=1, j=0	3	(1,0)	8	8	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
55	k=3, i=1, j=1	3	(1,1)	0	0	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
56	k=3, i=1, j=2	3	(1,2)	2	3	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
57	k=3, i=1, j=3	3	(1,3)	3	3	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
58	k=3, i=2, j=0	3	(2,0)	5	6	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
59	k=3, i=2, j=1	3	(2,1)	8	8	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
60	k=3, i=2, j=2	3	(2,2)	0	0	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
61	k=3, i=2, j=3	3	(2,3)	1	1	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
62	k=3, i=3, j=0	3	(3,0)	2	2	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
63	k=3, i=3, j=1	3	(3,1)	5	5	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
64	k=3, i=3, j=2	3	(3,2)	7	7	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
65	k=3, i=3, j=3	3	(3,3)	0	0	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
66	End	-	-	-	-	-	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]

💡 All intermediate nodes k processed; final shortest path matrix computed

Variable Tracker

Variable	Start	After k=0	After k=1	After k=2	After k=3	Final
dist	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,7,0]]	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]

Key Moments - 3 Insights

Why do we check if dist[i][k] + dist[k][j] < dist[i][j] instead of just dist[i][j]?

Because we want to see if going through the intermediate node k gives a shorter path from i to j. This is shown in execution_table rows like 9 and 11 where dist[i][j] updates after checking via k.

Why do some distances remain Infinity (∞) throughout the process?

Infinity means no path exists between those nodes. If no intermediate nodes connect them, the distance stays ∞, as seen in early rows before any updates.

Why do we update the matrix multiple times for the same pair (i,j)?

Because each intermediate node k might offer a shorter path. The matrix updates progressively, as seen in rows 20 and 37 where dist[0][2] and dist[0][3] get shorter.

Visual Quiz - 3 Questions

Look at the execution_table at step 11, what is the new distance from node 2 to node 1?

A 8

B Infinity

C 5

D 2

💡 Hint

Check the 'New dist[i][j]' column at step 11 for pair (2,1)

At which iteration does the distance from node 1 to node 3 first update to a finite value?

A Step 41

B Step 9

C Step 21

D Step 25

💡 Hint

Look for the first 'Yes' in 'Updated?' column for pair (1,3)

If the initial distance from node 0 to node 2 was 10 instead of Infinity, how would the matrix state change after k=1?

A No change, still 5

B It would remain 10

C It would update to 5

D It would update to 3

💡 Hint

Check how dist[0][2] updates at step 20 after considering k=1

Concept Snapshot

Floyd Warshall Algorithm:
- Uses dynamic programming on a distance matrix
- Iterates over all nodes as intermediate points k
- Updates dist[i][j] if dist[i][k] + dist[k][j] < dist[i][j]
- Handles negative edges but no negative cycles
- Final matrix shows shortest paths between all pairs

Full Transcript

Floyd Warshall algorithm finds shortest paths between all pairs of nodes in a graph. It starts with a distance matrix representing direct edges or infinity if no direct edge exists. Then, for each node k, it checks if using k as an intermediate node shortens the path between every pair (i,j). If yes, it updates the distance. This process repeats for all k, progressively improving the shortest paths. The final matrix shows the shortest distances between all nodes. Key points include checking if going through k is shorter, updating distances multiple times, and handling unreachable nodes with infinity.

Practice

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

easy

A. To detect cycles in a graph

B. To find the shortest path from a single source to all other vertices

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

D. To sort vertices in topological order

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: Differentiate from other algorithms

   Unlike Dijkstra's algorithm which finds shortest paths from one source, Floyd Warshall finds paths for all pairs.

3. Final Answer:

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

4. Quick Check:

   All pairs shortest path = Floyd Warshall [OK]

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

Common Mistakes:

• Confusing with Dijkstra's single source shortest path
• Thinking it detects cycles
• Assuming it sorts vertices

2. Which of the following is the correct way to initialize the distance matrix dist for Floyd Warshall in JavaScript given a graph adjacency matrix graph?

easy

A. const dist = graph.map(row => row.slice());

B. const dist = graph.slice();

C. const dist = graph.map(row => row);

D. const dist = [...graph];

Solution

1. Step 1: Understand deep copy necessity

   We need a deep copy of the 2D array so changes to dist do not affect graph.

2. Step 2: Check each option for deep copy

   const dist = graph.map(row => row.slice()); uses map and slice to copy each row array, creating a deep copy. Others create shallow copies.

3. Final Answer:

   const dist = graph.map(row => row.slice()); -> Option A

4. Quick Check:

   Deep copy with map and slice = const dist = graph.map(row => row.slice()); [OK]

Hint: Use map with slice for deep copy of 2D arrays [OK]

Common Mistakes:

• Using shallow copy causing original graph to change
• Using spread operator which copies only top-level array
• Using map without slice copying references

3. What will be the output distance matrix after running Floyd Warshall on the following graph adjacency matrix where Infinity means no direct edge?

const graph = [
  [0, 3, Infinity],
  [2, 0, 5],
  [Infinity, 1, 0]
];

medium

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

B. [[0, 3, 5], [2, 0, 5], [Infinity, 1, 0]]

C. [[0, 3, Infinity], [2, 0, 5], [3, 1, 0]]

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

Solution

1. Step 1: Initialize dist matrix same as graph

   dist = [[0,3,∞],[2,0,5],[∞,1,0]]

2. Step 2: Update dist using Floyd Warshall iterations

   Check paths through each vertex k=0,1,2:
   k=0: dist[2][0] = min(∞, dist[2][0]+dist[0][0])=∞ no change
   k=1: dist[0][2] = min(∞, dist[0][1]+dist[1][2])=3+5=8
   dist[2][0] = min(∞, dist[2][1]+dist[1][0])=1+2=3
   k=2: no shorter paths found
   Final dist = [[0,3,8],[2,0,5],[3,1,0]]

3. Final Answer:

   [[0, 3, 8], [2, 0, 5], [3, 1, 0]] -> Option D

4. Quick Check:

   Updated shortest paths matrix = [[0, 3, 8], [2, 0, 5], [3, 1, 0]] [OK]

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

Common Mistakes:

• Not updating paths through intermediate vertices
• Confusing Infinity with zero
• Missing updates for indirect paths

4. Identify the error in this Floyd Warshall implementation snippet:

for (let k = 0; k < V; k++) {
  for (let i = 0; i < V; i++) {
    for (let 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 if dist[i][k] or dist[k][j] is Infinity before addition

B. The loops should be reversed: i, j, then k

C. No error, the code is correct

D. The condition should use <= instead of <

Solution

1. Step 1: Analyze addition of distances

   Adding dist[i][k] + dist[k][j] without checking if either is Infinity can cause incorrect results or overflow.

2. Step 2: Identify missing Infinity checks

   Before adding, must ensure dist[i][k] !== Infinity and dist[k][j] !== Infinity to avoid invalid sums.

3. Final Answer:

   Missing check if dist[i][k] or dist[k][j] is Infinity before addition -> Option A

4. Quick Check:

   Check Infinity before sum to avoid errors [OK]

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

Common Mistakes:

• Ignoring Infinity causing wrong updates
• Changing loop order unnecessarily
• Using <= instead of < causing redundant updates

5. Given a weighted directed graph with possible negative edges but no negative cycles, how does Floyd Warshall detect the presence of a negative cycle after running the algorithm?

hard

A. By checking if any dist[i][j] is Infinity

B. By checking if any diagonal element dist[i][i] becomes negative

C. By verifying if the sum of all distances is zero

D. By checking if any dist[i][j] is negative for i != j

Solution

1. Step 1: Understand negative cycle effect on dist matrix

   Negative cycles cause the shortest path from a vertex to itself to become negative.

2. Step 2: Check diagonal elements after Floyd Warshall

   If any dist[i][i] < 0, it means a negative cycle exists involving vertex i.

3. Final Answer:

   By checking if any diagonal element dist[i][i] becomes negative -> Option B

4. Quick Check:

   Negative cycle detected if dist[i][i] < 0 [OK]

Hint: Check diagonal dist[i][i] for negativity to find negative cycles [OK]

Common Mistakes:

• Checking off-diagonal elements for negative cycles
• Confusing Infinity with negative cycles
• Assuming sum of distances indicates cycles