All Pair Shortest Path Floyd-Warshall Algorithm With Practical Example<\/p>\n
[fvplayer id=”118″]<\/p>\n
The Floyd-Warshall algorithm<\/strong> is a dynamic programming<\/strong> technique used to find the shortest paths between all pairs of vertices<\/strong> in a weighted graph. It works for both directed<\/strong> and undirected<\/strong> graphs with positive or negative weights<\/strong> (but no negative cycles).<\/p>\n Initialize the distance matrix<\/strong>:<\/p>\n Iterate through all nodes as intermediate vertices<\/strong>:<\/p>\n After all iterations<\/strong>, We have a directed graph with 4 vertices (A, B, C, D)<\/strong>:<\/p>\n (\u221e represents no direct edge between the nodes)<\/p>\n Final matrix gives the shortest path between every pair of nodes.<\/strong><\/p>\n The Floyd-Warshall algorithm runs in O(V\u00b3)<\/strong> time complexity, where Simple and easy to implement<\/strong> Does not work with graphs containing negative cycles<\/strong>\u00a0Key Concepts<\/strong><\/h3>\n
\n
(i, j)<\/code> represents the shortest distance from vertex i<\/code> to j<\/code>.<\/li>\nk<\/code> is an intermediate node.<\/li>\n<\/ul>\n\u00a0Algorithm Steps<\/strong><\/h3>\n
\n
i<\/code> and j<\/code>, set dist[i][j]<\/code> to its weight.<\/li>\ni == j<\/code>, set dist[i][j] = 0<\/code>.<\/li>\ndist[i][j] = \u221e<\/code>.<\/li>\n<\/ul>\n\n
k<\/code>, update dist[i][j]<\/code> for all pairs (i, j)<\/code>.<\/li>\nk<\/code>.<\/li>\n<\/ul>\ndist[i][j]<\/code> will contain the shortest path from i<\/code> to j<\/code>.<\/p>\n\u00a0Practical Example<\/strong><\/h3>\n
Example Graph (Adjacency Matrix Representation)<\/strong><\/h3>\n
\n\n
\n \nFrom \u2192 To<\/th>\n A<\/th>\n B<\/th>\n C<\/th>\n D<\/th>\n<\/tr>\n<\/thead>\n \n A<\/strong><\/td>\n 0<\/td>\n 3<\/td>\n \u221e<\/td>\n 7<\/td>\n<\/tr>\n \n B<\/strong><\/td>\n 8<\/td>\n 0<\/td>\n 2<\/td>\n \u221e<\/td>\n<\/tr>\n \n C<\/strong><\/td>\n 5<\/td>\n \u221e<\/td>\n 0<\/td>\n 1<\/td>\n<\/tr>\n \n D<\/strong><\/td>\n 2<\/td>\n \u221e<\/td>\n \u221e<\/td>\n 0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n \u00a0Step-by-Step Execution<\/strong><\/h3>\n
Initial Distance Matrix<\/strong><\/h4>\n
A<\/span> B<\/span> C D
\nA<\/span> [ 0 3 \u221e 7 ]<\/span>
\nB<\/span> [ 8 0 2 \u221e ]<\/span>
\nC [ 5 \u221e 0 1 ]<\/span>
\nD [ 2 \u221e \u221e 0 ]<\/span>
\n<\/code><\/div>\n<\/div>\nStep 1: Consider Node A (k = 0)<\/strong><\/h4>\n
\n
Step 2: Consider Node B (k = 1)<\/strong><\/h4>\n
\n
5 + 3 = 8<\/code>, shorter than \u221e<\/code><\/li>\n A<\/span> B<\/span> C D
\nA<\/span> [ 0 3 \u221e 7 ]<\/span>
\nB<\/span> [ 8 0 2 \u221e ]<\/span>
\nC [ 5 8 0 1 ]<\/span>
\nD [ 2 \u221e \u221e 0 ]<\/span>
\n<\/code><\/div>\n<\/div>\nStep 3: Consider Node C (k = 2)<\/strong><\/h4>\n
\n
2 + 1 = 3<\/code>, shorter than \u221e<\/code><\/li>\n A<\/span> B<\/span> C D
\nA<\/span> [ 0 3 5 7 ]<\/span>
\nB<\/span> [ 8 0 2 3 ]<\/span>
\nC [ 5 8 0 1 ]<\/span>
\nD [ 2 \u221e \u221e 0 ]<\/span>
\n<\/code><\/div>\n<\/div>\nStep 4: Consider Node D (k = 3)<\/strong><\/h4>\n
\n
7 + 1 = 6<\/code>, shorter than \u221e<\/code><\/li>\n3 + 1 = 4<\/code>, shorter than 2<\/code><\/li>\n A<\/span> B<\/span> C D
\nA<\/span> [ 0 3 5 6 ]<\/span>
\nB<\/span> [ 5 0 2 3 ]<\/span>
\nC [ 5 8 0 1 ]<\/span>
\nD [ 2 5 7 0 ]<\/span>
\n<\/code><\/div>\n<\/div>\n\u00a0Time Complexity<\/strong><\/h3>\n
V<\/code> is the number of vertices.<\/p>\n\u00a0Advantages<\/strong><\/h3>\n
Works with negative weights (but no negative cycles)<\/strong>
Finds shortest paths for all pairs in one execution<\/strong><\/p>\n\u00a0Disadvantages<\/strong><\/h3>\n
Less efficient than Dijkstra\u2019s Algorithm for sparse graphs<\/strong><\/p>\nPython Implementation<\/strong><\/h3>\n