Floyd Warshall All Pairs Shortest Path in DSA C - 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

↓

Update dist[i

↓

Repeat for all k

↓

Final shortest paths matrix

The algorithm updates shortest paths by considering each node as an intermediate point, improving distances step-by-step until all pairs shortest paths are found.

Execution Sample

DSA C

int dist[V][V] = {
  {0, 3, INF, 7},
  {8, 0, 2, INF},
  {5, INF, 0, 1},
  {2, INF, INF, 0}
};
// Floyd Warshall updates dist

This code initializes a graph's distance matrix and runs Floyd Warshall to find shortest paths between all pairs.

Execution Table

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

💡 All intermediate nodes k processed; final distance matrix contains shortest paths

Variable Tracker

Variable	Start	After k=0	After k=1	After k=2	After k=3	Final
dist	[[0,3,INF,7],[8,0,2,INF],[5,INF,0,1],[2,INF,INF,0]]	[[0,3,INF,7],[8,0,2,15],[5,8,0,1],[2,5,7,0]]	[[0,3,5,7],[8,0,2,15],[5,8,0,6],[2,5,7,0]]	[[0,3,5,6],[8,0,2,3],[5,8,0,6],[2,5,7,0]]	[[0,3,5,6],[8,0,2,3],[5,8,0,6],[2,5,7,0]]	[[0,3,5,6],[8,0,2,3],[5,8,0,6],[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 like 8 and 10 where updates happen only when the new path is shorter.

Why do we consider each node k as an intermediate node in order?

Considering nodes in order ensures that all shorter paths using nodes with smaller indices are found before using larger indices. This stepwise improvement is visible in variable_tracker where dist updates after each k.

What happens if there is no direct edge between nodes i and j initially?

We start with INF (infinity) for no direct edge. Floyd Warshall updates these to shorter paths if found via intermediate nodes, as seen in execution_table rows where INF changes to finite values.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the new dist[2][1] value?

A INF

B 8

C 5

D 2

💡 Hint

Check row with Step 10 in execution_table under 'New dist[i][j]' column

At which intermediate node k does dist[0][2] first get updated from INF to a finite value?

A k=0

B k=2

C k=1

D k=3

💡 Hint

Look at execution_table rows where pair (0,2) is updated; see when INF changes to 5

If we change the edge weight from node 1 to 3 from INF to 4 initially, how would the distance matrix change after k=1?

A dist[1][3] would be 4 instead of 15

B dist[0][3] would be 7 unchanged

C dist[2][3] would become 1 unchanged

D No changes in dist matrix

💡 Hint

Check how initial edge weights affect updates at k=1 in variable_tracker

Concept Snapshot

Floyd Warshall Algorithm:
- Uses dynamic programming on distance matrix
- Iterates over all nodes as intermediate k
- Updates dist[i][j] if dist[i][k] + dist[k][j] < dist[i][j]
- Finds shortest paths between all pairs
- Handles negative edges but no negative cycles
- Time complexity O(V^3)

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 weights and no edges are infinity. The algorithm picks each node as an intermediate point k and checks for every pair (i,j) if going through k gives a shorter path. If yes, it updates dist[i][j]. This process repeats for all nodes k. The execution table shows step-by-step updates of the distance matrix. The variable tracker shows how the matrix changes after each k iteration. Key moments clarify why updates happen only when shorter paths are found, why nodes are considered in order, and how infinite distances get updated. The visual quiz tests understanding of matrix updates and intermediate steps. The concept snapshot summarizes the algorithm's key points and complexity.