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
using System ; using System . Collections . Generic ; class GFG { static readonly int MAXN = 100 ; static int INF = ( int ) 1e7 ; static int [ , ] dis = new int [ MAXN , MAXN ] ; static int [ , ] Next = new int [ MAXN , MAXN ] ; static void initialise ( int V , 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 ; } } } static List < int > constructPath ( int u , int v ) { if ( Next [ u , v ] == - 1 ) return null ; List < int > path = new List < int > ( ) ; path . Add ( u ) ; while ( u != v ) { u = Next [ u , v ] ; path . Add ( u ) ; } return path ; } static 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 ] ; } } } } } static void printPath ( List < int > path ) { int n = path . Count ; for ( int i = 0 ; i < n - 1 ; i ++ ) Console . Write ( path [ i ] + " ▁ - > ▁ " ) ; Console . Write ( path [ n - 1 ] + " STRNEWLINE " ) ; } public static void Main ( String [ ] args ) { int V = 4 ; int [ , ] graph = { { 0 , 3 , INF , 7 } , { 8 , 0 , 2 , INF } , { 5 , INF , 0 , 1 } , { 2 , INF , INF , 0 } } ; initialise ( V , graph ) ; floydWarshall ( V ) ; List < int > path ; Console . Write ( " Shortest ▁ path ▁ from ▁ 1 ▁ to ▁ 3 : ▁ " ) ; path = constructPath ( 1 , 3 ) ; printPath ( path ) ; Console . Write ( " Shortest ▁ path ▁ from ▁ 0 ▁ to ▁ 2 : ▁ " ) ; path = constructPath ( 0 , 2 ) ; printPath ( path ) ; Console . Write ( " Shortest ▁ path ▁ from ▁ 3 ▁ to ▁ 2 : ▁ " ) ; path = constructPath ( 3 , 2 ) ; printPath ( path ) ; } }