Finding shortest path between any two nodes using Floyd Warshall Algorithm | 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
def initialise ( V ) : NEW_LINE INDENT global dis , Next NEW_LINE for i in range ( V ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT dis [ i ] [ j ] = graph [ i ] [ j ] NEW_LINE if ( graph [ i ] [ j ] == INF ) : NEW_LINE INDENT Next [ i ] [ j ] = - 1 NEW_LINE DEDENT else : NEW_LINE INDENT Next [ i ] [ j ] = j NEW_LINE DEDENT DEDENT DEDENT DEDENT def constructPath ( u , v ) : NEW_LINE INDENT global graph , Next NEW_LINE if ( Next [ u ] [ v ] == - 1 ) : NEW_LINE INDENT return { } NEW_LINE DEDENT path = [ u ] NEW_LINE while ( u != v ) : NEW_LINE INDENT u = Next [ u ] [ v ] NEW_LINE path . append ( u ) NEW_LINE DEDENT return path NEW_LINE DEDENT def floydWarshall ( V ) : NEW_LINE INDENT global dist , Next NEW_LINE for k in range ( V ) : NEW_LINE INDENT for i in range ( V ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT if ( dis [ i ] [ k ] == INF or dis [ k ] [ j ] == INF ) : NEW_LINE INDENT continue NEW_LINE DEDENT if ( dis [ i ] [ j ] > dis [ i ] [ k ] + dis [ k ] [ j ] ) : NEW_LINE INDENT dis [ i ] [ j ] = dis [ i ] [ k ] + dis [ k ] [ j ] NEW_LINE Next [ i ] [ j ] = Next [ i ] [ k ] NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT def printPath ( path ) : NEW_LINE INDENT n = len ( path ) NEW_LINE for i in range ( n - 1 ) : NEW_LINE INDENT print ( path [ i ] , end = " ▁ - > ▁ " ) NEW_LINE DEDENT print ( path [ n - 1 ] ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT MAXM , INF = 100 , 10 ** 7 NEW_LINE dis = [ [ - 1 for i in range ( MAXM ) ] for i in range ( MAXM ) ] NEW_LINE Next = [ [ - 1 for i in range ( MAXM ) ] for i in range ( MAXM ) ] NEW_LINE V = 4 NEW_LINE graph = [ [ 0 , 3 , INF , 7 ] , [ 8 , 0 , 2 , INF ] , [ 5 , INF , 0 , 1 ] , [ 2 , INF , INF , 0 ] ] NEW_LINE initialise ( V ) NEW_LINE floydWarshall ( V ) NEW_LINE path = [ ] NEW_LINE print ( " Shortest ▁ path ▁ from ▁ 1 ▁ to ▁ 3 : ▁ " , end = " " ) NEW_LINE path = constructPath ( 1 , 3 ) NEW_LINE printPath ( path ) NEW_LINE print ( " Shortest ▁ path ▁ from ▁ 0 ▁ to ▁ 2 : ▁ " , end = " " ) NEW_LINE path = constructPath ( 0 , 2 ) NEW_LINE printPath ( path ) NEW_LINE print ( " Shortest ▁ path ▁ from ▁ 3 ▁ to ▁ 2 : ▁ " , end = " " ) NEW_LINE path = constructPath ( 3 , 2 ) NEW_LINE printPath ( path ) NEW_LINE DEDENT