Sum of all pair shortest paths in a Tree | C # 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 readonly 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
using System ; class GFG { static readonly int INF = 99999 ; static int floyd_warshall ( int [ , ] graph , int V ) { int [ , ] dist = new int [ V , V ] ; int 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 ] ; } } } } int sum = 0 ; for ( i = 0 ; i < V ; i ++ ) { for ( j = i + 1 ; j < V ; j ++ ) { sum += dist [ i , j ] ; } } return sum ; } static int sumOfshortestPath ( int N , int E , int [ , ] edges ) { int [ , ] g = new int [ N , N ] ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { g [ i , j ] = INF ; } } for ( int i = 0 ; i < E ; i ++ ) { int u = edges [ i , 0 ] ; int v = edges [ i , 1 ] ; int w = edges [ i , 2 ] ; g [ u , v ] = w ; g [ v , u ] = w ; } return floyd_warshall ( g , N ) ; } public static void Main ( String [ ] args ) { int N = 4 ; int E = 3 ; int [ , ] Edges = { { 0 , 1 , 1 } , { 1 , 2 , 2 } , { 2 , 3 , 3 } } ; Console . Write ( sumOfshortestPath ( N , E , Edges ) ) ; } }