Trees and Graphs‎ > ‎

Undirected Graph Sum

Given a undirected graph with weights, return the sum of the weight of each path between two nodes (no negative edges).

Input:
       A
       | 1
       B
   2 /   \ 3
    C     D
    
Output:
18
since 
A to B has weight 1
A to C has weight 3
A to D has weight 4
B to C has weight 2
B to D has weight 3
C to D has weight 5
Solution:
Using Floyd-Warshall algorithm get the 2 dimensional array of path costs:

  A B C D
A 0 1 3 4
B 1 0 2 3
C 3 2 0 5
D 4 3 5 0

The sum of top right triangle (shown in bold) is the answer.


Comments