Finding shortest path between any two nodes using Floyd Warshall Algorithm | C ++ program to find the shortest path between any two nodes using Floyd Warshall Algorithm . ; Infinite value for array ; Initializing the distance and Next array ; No edge between node i and j ; Function construct the shortest path between u and v ; If there 's no path between  node u and v, simply return  an empty array ; Storing the path in a vector ; Standard Floyd Warshall Algorithm with little modification Now if we find that dis [ i ] [ j ] > dis [ i ] [ k ] + dis [ k ] [ j ] then we modify next [ i ] [ j ] = next [ i ] [ k ] ; We cannot travel through edge that doesn 't exist ; Print the shortest path ; Driver code ; Function to initialise the distance and Next array ; Calling Floyd Warshall Algorithm , this will update the shortest distance as well as Next array ; Path from node 1 to 3 ; Path from node 0 to 2 ; path from node 3 to 2
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAXN  100 NEW_LINE const int INF = 1e7 ; int dis [ MAXN ] [ MAXN ] ; int Next [ MAXN ] [ MAXN ] ; void initialise ( int V , vector < vector < int > > & graph ) { for ( int i = 0 ; i < V ; i ++ ) { for ( int j = 0 ; j < V ; j ++ ) { dis [ i ] [ j ] = graph [ i ] [ j ] ; if ( graph [ i ] [ j ] == INF ) Next [ i ] [ j ] = -1 ; else Next [ i ] [ j ] = j ; } } } vector < int > constructPath ( int u , int v ) { if ( Next [ u ] [ v ] == -1 ) return { } ; vector < int > path = { u } ; while ( u != v ) { u = Next [ u ] [ v ] ; path . push_back ( u ) ; } return path ; } void floydWarshall ( int V ) { for ( int k = 0 ; k < V ; k ++ ) { for ( int i = 0 ; i < V ; i ++ ) { for ( int j = 0 ; j < V ; j ++ ) { if ( dis [ i ] [ k ] == INF dis [ k ] [ j ] == INF ) continue ; if ( dis [ i ] [ j ] > dis [ i ] [ k ] + dis [ k ] [ j ] ) { dis [ i ] [ j ] = dis [ i ] [ k ] + dis [ k ] [ j ] ; Next [ i ] [ j ] = Next [ i ] [ k ] ; } } } } } void printPath ( vector < int > & path ) { int n = path . size ( ) ; for ( int i = 0 ; i < n - 1 ; i ++ ) cout << path [ i ] << " ▁ - > ▁ " ; cout << path [ n - 1 ] << endl ; } int main ( ) { int V = 4 ; vector < vector < int > > graph = { { 0 , 3 , INF , 7 } , { 8 , 0 , 2 , INF } , { 5 , INF , 0 , 1 } , { 2 , INF , INF , 0 } } ; initialise ( V , graph ) ; floydWarshall ( V ) ; vector < int > path ; cout << " Shortest ▁ path ▁ from ▁ 1 ▁ to ▁ 3 : ▁ " ; path = constructPath ( 1 , 3 ) ; printPath ( path ) ; cout << " Shortest ▁ path ▁ from ▁ 0 ▁ to ▁ 2 : ▁ " ; path = constructPath ( 0 , 2 ) ; printPath ( path ) ; cout << " Shortest ▁ path ▁ from ▁ 3 ▁ to ▁ 2 : ▁ " ; path = constructPath ( 3 , 2 ) ; printPath ( path ) ; return 0 ; }