Compute average values for all vertices using weights of shortest paths store in dp .
for ( int i = 0 ; i < V ; i ++ ) { if ( dp [ V ] [ i ] != -1 ) { for ( int j = 0 ; j < V ; j ++ ) if ( dp [ j ] [ i ] != -1 ) avg [ i ] = max ( avg [ i ] , ( ( double ) dp [ V ] [ i ] - dp [ j ] [ i ] ) / ( V - j ) ) ; } }