# Algorithm to calculate average weight from every pair of nodes [duplicate]

I'm trying to solve a puzzle where I need to calculate the average weight between every node in the graph.

For example, for the following graph:

The results is calculated like this:

1 -> 2 = 3;

1 -> 3 = 7;

1 -> 4 = 5;

2 -> 3 = 4;

2 -> 4 = 2;

3 -> 4 = 7;

Average = 3+7+5+4+2+7 / 6;

NOTE: I'm visualizing the problem as a Graph, I might be wrong. The following constraints apply to this problem:

There is exactly one path between any two nodes, but all nodes are connected to every other node.

So we can assume that in the example, there will not be a path from 1 -> 4 directly

I'm looking for a recommendation of an algorithm that I can study in order to solve this type of problems. Not the actual solution.

One possible approach is Floyd-Warshall algorithm. This algorithm computes shortest paths between each pair of nodes. Since there is only one path between each pair of nodes, the shortest path will correspond to the weight of path between each pair of nodes. After computing all shortest paths you sum them and divide by the total number of paths (which is trivial given the number of nodes). This algorithm works in $O(|V|^3)$ time.
• @rus9384 A trivial quadratic time algorithm is just run DFS starting from each node and update each path if it is not computed yet. DFS takes $O(n)$ time and since it runs for each node it is $O(n^2)$. – fade2black Sep 21 '17 at 7:36