Floyd Warshall All Pairs Shortest Path in DSA Typescript - 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 + k->j < i->j

Yes/No↓

Update distance[i

↓

Repeat for all i, j

↓

Repeat for all k

↓

Final shortest paths matrix

The algorithm updates shortest paths by checking if going through an intermediate node k improves the path between every pair (i, j).

Execution Sample

DSA Typescript

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

This code runs Floyd Warshall on a 4-node graph to find shortest paths between all pairs.

Execution Table

Step	Operation	Indices (k,i,j)	Distance Before	Distance After	Visual State
1	Initialize distance matrix	-	-	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]	┌─────┬─────┬───────┬───────┐ │ 0 │ 3 │ ∞ │ 7 │ ├─────┼─────┼───────┼───────┤ │ 8 │ 0 │ 2 │ ∞ │ ├─────┼─────┼───────┼───────┤ │ 5 │ ∞ │ 0 │ 1 │ ├─────┼─────┼───────┼───────┤ │ 2 │ ∞ │ ∞ │ 0 │ └─────┴─────┴───────┴───────┘
2	k=0, i=1, j=3: Check if dist[1][0] + dist[0][3] < dist[1][3]	(0,1,3)	dist[1][3] = ∞	dist[1][3] = dist[1][0] + dist[0][3] = 8 + 7 = 15	Updated dist[1][3] from ∞ to 15
3	k=0, i=2, j=1: Check if dist[2][0] + dist[0][1] < dist[2][1]	(0,2,1)	dist[2][1] = ∞	dist[2][1] = dist[2][0] + dist[0][1] = 5 + 3 = 8	Updated dist[2][1] from ∞ to 8
4	k=0, i=3, j=1: Check if dist[3][0] + dist[0][1] < dist[3][1]	(0,3,1)	dist[3][1] = ∞	dist[3][1] = dist[3][0] + dist[0][1] = 2 + 3 = 5	Updated dist[3][1] from ∞ to 5
5	k=1, i=0, j=2: Check if dist[0][1] + dist[1][2] < dist[0][2]	(1,0,2)	dist[0][2] = ∞	dist[0][2] = dist[0][1] + dist[1][2] = 3 + 2 = 5	Updated dist[0][2] from ∞ to 5
6	k=1, i=3, j=2: Check if dist[3][1] + dist[1][2] < dist[3][2]	(1,3,2)	dist[3][2] = ∞	dist[3][2] = dist[3][1] + dist[1][2] = 5 + 2 = 7	Updated dist[3][2] from ∞ to 7
7	k=2, i=0, j=3: Check if dist[0][2] + dist[2][3] < dist[0][3]	(2,0,3)	dist[0][3] = 7	dist[0][3] = dist[0][2] + dist[2][3] = 5 + 1 = 6	Updated dist[0][3] from 7 to 6
8	k=2, i=1, j=3: Check if dist[1][2] + dist[2][3] < dist[1][3]	(2,1,3)	dist[1][3] = 15	dist[1][3] = dist[1][2] + dist[2][3] = 2 + 1 = 3	Updated dist[1][3] from 15 to 3
9	k=3, i=2, j=0: Check if dist[2][3] + dist[3][0] < dist[2][0]	(3,2,0)	dist[2][0] = 5	dist[2][0] = dist[2][3] + dist[3][0] = 1 + 2 = 3	Updated dist[2][0] from 5 to 3
10	k=3, i=2, j=1: Check if dist[2][3] + dist[3][1] < dist[2][1]	(3,2,1)	dist[2][1] = 8	dist[2][1] = dist[2][3] + dist[3][1] = 1 + 5 = 6	Updated dist[2][1] from 8 to 6
11	Final distance matrix	-	-	[[0,3,5,6],[8,0,2,3],[3,6,0,1],[2,5,7,0]]	┌───┬───┬───┬───┐ │ 0 │ 3 │ 5 │ 6 │ ├───┼───┼───┼───┤ │ 8 │ 0 │ 2 │ 3 │ ├───┼───┼───┼───┤ │ 3 │ 6 │ 0 │ 1 │ ├───┼───┼───┼───┤ │ 2 │ 5 │ 7 │ 0 │ └───┴───┴───┴───┘

💡 All intermediate nodes k processed; shortest paths finalized.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	Final
dist	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]	[[0,3,∞,7],[8,0,2,15],[5,∞,0,1],[2,∞,∞,0]]	[[0,3,∞,7],[8,0,2,15],[5,8,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,∞,0]]	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,7,0]]	[[0,3,5,6],[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],[3,8,0,1],[2,5,7,0]]	[[0,3,5,6],[8,0,2,3],[3,6,0,1],[2,5,7,0]]	[[0,3,5,6],[8,0,2,3],[3,6,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 updating dist[i][j]?

Because we only update dist[i][j] if going through node k gives a shorter path. This is shown in execution_table rows 2-10 where updates happen only when the new path is shorter.

What does 'Infinity' mean in the distance matrix at the start?

'Infinity' means no direct path exists between those nodes initially. The algorithm tries to find shorter paths through intermediate nodes, replacing Infinity with actual distances if found, as seen in steps 2, 3, 4, 5, and 6.

Why do we repeat the process for all k from 0 to n-1?

Because each k represents an intermediate node that might improve paths between all pairs (i, j). The algorithm ensures all possible intermediate nodes are considered, as shown by the repeated steps for k=0,1,2,3.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the updated distance from node 0 to node 2?

A 5

B ∞

C 3

D 2

💡 Hint

Check the 'Distance After' column at step 5 in execution_table.

At which step does the distance from node 1 to node 3 first get updated to a finite value?

A Step 8

B Step 5

C Step 2

D Step 10

💡 Hint

Look for the first update of dist[1][3] in execution_table rows.

If the initial distance from node 3 to node 1 was 4 instead of Infinity, how would the distance from node 3 to node 2 change after step 6?

A It would become 6

B It would remain 7

C It would become 4

D It would become 9

💡 Hint

Check how dist[3][2] is updated at step 6 using dist[3][1] + dist[1][2].

Concept Snapshot

Floyd Warshall Algorithm:
- Uses a distance matrix dist[n][n]
- For each intermediate node k:
  For each pair (i,j):
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
- Finds shortest paths between all pairs
- Handles negative edges but no negative cycles

Full Transcript

Floyd Warshall algorithm finds shortest paths between all pairs of nodes in a graph. It starts with a distance matrix where direct edges have their weights and no edges are marked as Infinity. It then iteratively considers each node as an intermediate point k. For every pair of nodes (i, j), it checks if going through k gives a shorter path than the current known path. If yes, it updates the distance. This process repeats for all k, ensuring all possible intermediate nodes are considered. The final matrix shows the shortest distances between every pair of nodes. The algorithm handles graphs with negative edges but assumes no negative cycles. The execution table shows step-by-step updates of the distance matrix, and the variable tracker records the matrix state after each update.

Practice

1. What does Floyd-Warshall compute that single-source shortest path algorithms like Dijkstra do not?

easy

A. Shortest path from one source to all vertices

B. Shortest paths between ALL pairs of vertices in one run

C. Minimum spanning tree of the graph

D. Topological order of vertices

Solution

1. Step 1: Single-source vs all-pairs

   Dijkstra/Bellman-Ford compute shortest paths from ONE source to all others. To get all-pairs with Dijkstra, run it V times = O(V(E + V log V)).

2. Step 2: Floyd-Warshall

   Floyd-Warshall computes shortest paths between every pair (i,j) in a single O(V³) pass. Simpler to implement for dense graphs.

3. Final Answer:

   All-pairs shortest paths in one pass. -> Option B

4. Quick Check:

   Floyd-Warshall = all-pairs. Dijkstra = single-source. [OK]

Hint: Floyd-Warshall = all-pairs shortest path. O(V³) time, O(V²) space. [OK]

Common Mistakes:

• Confusing with Dijkstra (single-source)
• Thinking it finds MST
• Confusing with topological sort

2. What is the Floyd-Warshall recurrence? dist[i][j] after considering vertex k as intermediate is:

medium

A. dist[i][j] = dist[i][k] + dist[k][j]

B. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

C. dist[i][j] = max(dist[i][j], dist[i][k] + dist[k][j])

D. dist[i][j] = dist[i][k] * dist[k][j]

Solution

1. Step 1: Core idea

   For each intermediate vertex k: is the path i→k→j shorter than the current best i→j?

2. Step 2: Recurrence

   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Keep the minimum of: current best OR going through k.

3. Final Answer:

   min(dist[i][j], dist[i][k] + dist[k][j]) -> Option B

4. Quick Check:

   Always take the minimum - relaxation. [OK]

Hint: Floyd-Warshall: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Relax via each intermediate k. [OK]

Common Mistakes:

• Using + without min (overwrites current best)
• Using max instead of min
• Multiplying instead of adding edge weights

3. In TypeScript, how do you initialize dist[i][i] and dist[i][j] (no direct edge) for Floyd-Warshall?

medium

A. dist[i][i] = 0, dist[i][j] = -1

B. dist[i][i] = 0, dist[i][j] = Infinity

C. dist[i][i] = 1, dist[i][j] = 0

D. dist[i][i] = Infinity, dist[i][j] = Infinity

Solution

1. Step 1: Self-distance

   dist[i][i] = 0 - zero cost to stay at the same vertex.

2. Step 2: No edge

   dist[i][j] = Infinity when no direct edge exists - represents unreachable initially. In TypeScript: Infinity works correctly with Math.min().

3. Final Answer:

   dist[i][i]=0, no edge=Infinity -> Option B

4. Quick Check:

   Self=0, no edge=Infinity. Infinity + x = Infinity in JS - works with min(). [OK]

Hint: Init: self=0, no edge=Infinity. TypeScript Infinity works correctly with Math.min(). [OK]

Common Mistakes:

• Using -1 for no edge (breaks min comparison)
• Setting self-distance to Infinity
• Using 0 for no edge (treats as zero-weight edge)

4. What is the correct loop order for Floyd-Warshall in TypeScript?

hard

A. for i → for j → for k

B. for k → for i → for j

C. for i → for k → for j

D. for j → for k → for i

Solution

1. Step 1: Why k is outermost

   k is the intermediate vertex being 'unlocked' at each outer iteration. When we process intermediate k, all pairs i→j must be relaxed using k.

2. Step 2: Correctness

   If k is innermost, we might use a later-unlocked vertex when relaxing - violating the DP ordering. k must be outermost so all (i,j) pairs are fully relaxed before moving to k+1.

3. Final Answer:

   k outermost, then i, then j. -> Option B

4. Quick Check:

   Floyd-Warshall loop order: k→i→j. k must be outermost. [OK]

Hint: Loop order: k (intermediate) → i (source) → j (dest). k must be outermost - critical for correctness. [OK]

Common Mistakes:

• Putting i outermost (most common mistake)
• Putting j outermost
• Any order other than k→i→j gives wrong results

5. How do you detect a negative cycle using Floyd-Warshall after completion?

hard

A. Check if any dist[i][j] === -Infinity

B. Check if any dist[i][i] < 0 - a vertex with negative self-distance indicates a negative cycle

C. Check if the total sum of all dist values is negative

D. Run the algorithm a second time and compare results

Solution

1. Step 1: Negative cycle effect

   If a negative cycle exists reachable from i back to i, the shortest path dist[i][i] will become negative (going around the cycle reduces cost below 0).

2. Step 2: Detection

   After the algorithm completes, check: for any i, if dist[i][i] < 0, a negative cycle exists involving i.

3. Final Answer:

   Check dist[i][i] < 0 for any i. -> Option B

4. Quick Check:

   Negative cycle: dist[i][i] < 0 after Floyd-Warshall. [OK]

Hint: Negative cycle detection: dist[i][i] < 0 after Floyd-Warshall. Self-distance going negative = cycle. [OK]

Common Mistakes:

• Checking dist[i][j] for non-self pairs
• Summing all distances
• Running algorithm twice