Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Floyd-Warshall Algorithm
Bookmark
Input
4x4 Matrix
4x4 DAG
5x5 Cycle
Custom
matrix
=
[[0,3,null,5],[2,0,null,4],[null,1,0,null],[null,null,2,0]]
Floyd-Warshall Algorithm
Intermediate Node: k = undefined
Graph
3
5
2
4
1
2
0
1
2
3
Distance Matrix
0
1
2
3
0
0
3
∞
5
1
2
0
∞
4
2
∞
1
0
∞
3
∞
∞
2
0
Legend:
Default
Current
Path
k-node
Updated
Floyd-Warshall Algorithm
Intermediate Node: k = undefined
Graph
3
5
2
4
1
2
0
1
2
3
Distance Matrix
0
1
2
3
0
0
3
∞
5
1
2
0
∞
4
2
∞
1
0
∞
3
∞
∞
2
0
Legend:
Default
Current
Path
k-node
Updated
Floyd-Warshall Algorithm
Intermediate Node: k = 0
Graph
3
5
2
4
1
2
0
1
2
3
Distance Matrix
j=2
i=1
0
1
2
3
0
0
3
∞
5
1
2
0
∞
4
2
∞
1
0
∞
3
∞
∞
2
0
Checking: dist[1][2] vs dist[1][0] + dist[0][2]
∞ vs 2 + ∞ = ∞
Legend:
Default
Current
Path
k-node
Updated
Floyd-Warshall Algorithm
Intermediate Node: k = 0
Graph
3
5
2
4
1
2
0
1
2
3
Distance Matrix
j=2
i=3
0
1
2
3
0
0
3
∞
5
1
2
0
∞
4
2
∞
1
0
∞
3
∞
∞
2
0
Checking: dist[3][2] vs dist[3][0] + dist[0][2]
2 vs ∞ + ∞ = ∞
Legend:
Default
Current
Path
k-node
Updated
Floyd-Warshall Algorithm
Intermediate Node: k = 1
Graph
3
5
2
4
1
2
0
1
2
3
Distance Matrix
j=1
i=1
0
1
2
3
0
0
3
∞
5
1
2
0
∞
4
2
∞
1
0
∞
3
∞
∞
2
0
Checking: dist[1][1] vs dist[1][1] + dist[1][1]
0 vs 0 + 0 = 0
Legend:
Default
Current
Path
k-node
Updated
Floyd-Warshall Algorithm
Intermediate Node: k = 1
Graph
3
5
2
4
3
1
5
2
0
1
2
3
Distance Matrix
j=0
i=3
0
1
2
3
0
0
3
∞
5
1
2
0
∞
4
2
3
1
0
5
3
∞
∞
2
0
Checking: dist[3][0] vs dist[3][1] + dist[1][0]
∞ vs ∞ + 2 = ∞
Legend:
Default
Current
Path
k-node
Updated
Floyd-Warshall Algorithm
Intermediate Node: k = 2
Graph
3
5
2
4
3
1
5
2
0
1
2
3
Distance Matrix
j=3
i=0
0
1
2
3
0
0
3
∞
5
1
2
0
∞
4
2
3
1
0
5
3
∞
∞
2
0
Checking: dist[0][3] vs dist[0][2] + dist[2][3]
5 vs ∞ + 5 = ∞
Legend:
Default
Current
Path
k-node
Updated
Floyd-Warshall Algorithm
Intermediate Node: k = 2
Graph
3
5
2
4
3
1
5
2
0
1
2
3
Distance Matrix
j=2
i=2
0
1
2
3
0
0
3
∞
5
1
2
0
∞
4
2
3
1
0
5
3
∞
∞
2
0
Checking: dist[2][2] vs dist[2][2] + dist[2][2]
0 vs 0 + 0 = 0
Legend:
Default
Current
Path
k-node
Updated
Floyd-Warshall Algorithm
Intermediate Node: k = 3
Graph
3
5
2
4
3
1
5
5
3
2
0
1
2
3
Distance Matrix
j=1
i=0
0
1
2
3
0
0
3
∞
5
1
2
0
∞
4
2
3
1
0
5
3
5
3
2
0
Checking: dist[0][1] vs dist[0][3] + dist[3][1]
3 vs 5 + 3 = 8
Legend:
Default
Current
Path
k-node
Updated
Floyd-Warshall Algorithm
Intermediate Node: k = 3
Graph
3
7
5
2
6
4
3
1
5
5
3
2
0
1
2
3
Distance Matrix
j=1
i=2
0
1
2
3
0
0
3
7
5
1
2
0
6
4
2
3
1
0
5
3
5
3
2
0
Checking: dist[2][1] vs dist[2][3] + dist[3][1]
1 vs 5 + 3 = 8
Legend:
Default
Current
Path
k-node
Updated
Floyd-Warshall Algorithm
All-pairs shortest paths computed
Graph
3
7
5
2
6
4
3
1
5
5
3
2
0
1
2
3
Distance Matrix
j=3
i=3
0
1
2
3
0
0
3
7
5
1
2
0
6
4
2
3
1
0
5
3
5
3
2
0
Checking: dist[3][3] vs dist[3][3] + dist[3][3]
0 vs 0 + 0 = 0
Legend:
Default
Current
Path
k-node
Updated
algo
master
.
io
Step:
Initialize distance matrix with direct edge weights (∞ = no direct edge)
0 / 137
Input
4x4 Matrix
4x4 DAG
5x5 Cycle
Custom
matrix
=
[[0,3,null,5],[2,0,null,4],[null,1,0,null],[null,null,2,0]]
0 / 137
algo
master
.
io
Step:
Initialize distance matrix with direct edge weights (∞ = no direct edge)
