Sum of all pair shortest paths in a Tree | Javascript 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 ; Number of Vertices ; Number of Edges ; Given Edges with weight ; Function Call
let INF = 99999 ; function floyd_warshall ( graph , V ) { let dist = new Array ( V ) ; for ( let i = 0 ; i < V ; i ++ ) { dist [ i ] = new Array ( V ) ; } let i , j , k ; for ( i = 0 ; i < V ; i ++ ) { for ( j = 0 ; j < V ; j ++ ) { dist [ i ] [ j ] = graph [ i ] [ j ] ; } } for ( k = 0 ; k < V ; k ++ ) { for ( i = 0 ; i < V ; i ++ ) { for ( j = 0 ; j < V ; j ++ ) { if ( dist [ i ] [ k ] + dist [ k ] [ j ] < dist [ i ] [ j ] ) { dist [ i ] [ j ] = dist [ i ] [ k ] + dist [ k ] [ j ] ; } } } } let sum = 0 ; for ( i = 0 ; i < V ; i ++ ) { for ( j = i + 1 ; j < V ; j ++ ) { sum += dist [ i ] [ j ] ; } } return sum ; } function sumOfshortestPath ( N , E , edges ) { let g = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) { g [ i ] = new Array ( N ) ; for ( let j = 0 ; j < N ; j ++ ) { g [ i ] [ j ] = INF ; } } for ( let i = 0 ; i < E ; i ++ ) { let u = edges [ i ] [ 0 ] ; let v = edges [ i ] [ 1 ] ; let w = edges [ i ] [ 2 ] ; g [ u ] [ v ] = w ; g [ v ] [ u ] = w ; } return floyd_warshall ( g , N ) ; } let N = 4 ; let E = 3 ; let Edges = [ [ 0 , 1 , 1 ] , [ 1 , 2 , 2 ] , [ 2 , 3 , 3 ] ] ; document . write ( sumOfshortestPath ( N , E , Edges ) ) ;