Sum of all pair shortest paths in a Tree | Python3 program for the above approach ; Function that performs the Floyd Warshall to find all shortest paths ; Initialize the distance matrix ; Pick all vertices as source one by one ; Pick all vertices as destination for the above picked source ; If vertex k is on the shortest path from i to j then update dist [ i ] [ j ] ; Sum the upper diagonal of the shortest distance matrix ; Traverse the given dist [ ] [ ] ; Add the distance ; Return the final sum ; Function to generate the tree ; Add edges ; Get source and destination with weight ; Add the edges ; Perform Floyd Warshal Algorithm ; Driver code ; Number of Vertices ; Number of Edges ; Given Edges with weight ; Function Call
INF = 99999 NEW_LINE def floyd_warshall ( graph , V ) : NEW_LINE INDENT dist = [ [ 0 for i in range ( V ) ] for i in range ( V ) ] NEW_LINE for i in range ( V ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT dist [ i ] [ j ] = graph [ i ] [ j ] NEW_LINE DEDENT DEDENT 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 ( dist [ i ] [ k ] + dist [ k ] [ j ] < dist [ i ] [ j ] ) : NEW_LINE INDENT dist [ i ] [ j ] = dist [ i ] [ k ] + dist [ k ] [ j ] NEW_LINE DEDENT DEDENT DEDENT DEDENT sum = 0 NEW_LINE for i in range ( V ) : NEW_LINE INDENT for j in range ( i + 1 , V ) : NEW_LINE INDENT sum += dist [ i ] [ j ] NEW_LINE DEDENT DEDENT return sum NEW_LINE DEDENT def sumOfshortestPath ( N , E , edges ) : NEW_LINE INDENT g = [ [ INF for i in range ( N ) ] for i in range ( N ) ] NEW_LINE for i in range ( E ) : NEW_LINE INDENT u = edges [ i ] [ 0 ] NEW_LINE v = edges [ i ] [ 1 ] NEW_LINE w = edges [ i ] [ 2 ] NEW_LINE g [ u ] [ v ] = w NEW_LINE g [ v ] [ u ] = w NEW_LINE DEDENT return floyd_warshall ( g , N ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 4 NEW_LINE E = 3 NEW_LINE Edges = [ [ 0 , 1 , 1 ] , [ 1 , 2 , 2 ] , [ 2 , 3 , 3 ] ] NEW_LINE print ( sumOfshortestPath ( N , E , Edges ) ) NEW_LINE DEDENT