1
$\begingroup$

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:

enter image description here

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.

$\endgroup$
0
$\begingroup$

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.

Also note that your graph is a tree. You may take a time to think over better algorithm which would work faster.

$\endgroup$
  • $\begingroup$ There is a quadratic algorithm. But OP might want to look at nodes that have a single neighbor first. $\endgroup$ – rus9384 Sep 21 '17 at 7:33
  • $\begingroup$ @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)$. $\endgroup$ – fade2black Sep 21 '17 at 7:36
  • $\begingroup$ Yes, somehow like it. I thought about BFS, with changing passed edges to directed ones. $\endgroup$ – rus9384 Sep 21 '17 at 7:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.