CODEWITHSUNDEEP
algorithmgraphgraph-theory
user6106260
user6106260

Reputation:

Total pairwise costs in a weighted undirected graph

Consider that we have a weighted undirected graph where, for any two vertices, there is a unique path that connects them. There are n vertices and n - 1 edges and the cost of each road is c_i.

Now, if every path that connects two given vertices has a certain cost that depends on the roads it passes by, how can we compute the total cost between all pairs of cities efficiently?

For example, the cost of each path can be the sum of the first road and the last road it passes by, or the sum of some power of the costs of each road it passes by, or the the maximum of the costs minus the minimum of the costs of the roads it passes by : Any formula that depends on the costs of the roads.

What algorithm to use in order to solve the problem efficiently ?

Upvotes: 2

Views: 698

Answers (2)

Petar Petrovic
Petar Petrovic

Reputation: 414

For any path p, let max(p) and min(p) denote the max and min cost of the road it passes by. Then Total_cost = sum for all path p [max(p) - min(p)]

Then sum for all path p max(p) can be found by the following way

Let G=(V,E) be the input graph, which should be a tree
Create a graph G' with vertices set V and no edges
Insert every edge in E to G' from lowest cost to hightest cost

Everytime you insert an edge e, it will connect two components S, T, and you can see that for every path p from S to T, max(p) = cost(e) So you can find sum for all path p max(p) by summing them. To connect two components efficiently, I think you can use the idea from Kruskal's algorithm.

Similarly, you can find sum for all path p min(p) and finally the total cost.

Upvotes: 1

amit
amit

Reputation: 178451

For each edge {u,v} in your graph, by "removing" it, you get two disconnected components, let them be U and V.

This means, the edge {u,v} is a part of the path going from each node in U to each node in V in the original graph, and there are |U| * |V| such paths.
This means, the problem boils down to calculate the sizes of these sets.

One way to do it, is choose arbitrary vertex r, and "make it the root" by making all edges directed, form r outwards. You got yourself a rooted directed tree after you do it.

By traversing the tree once in linear time, you can now find the size of each subtree:

size(u) = sum { size(v} | v is a child of u}  + 1

After you have calculated the size of all subtrees, for each directed edge (u,v), the sizes of original sets |V| and |U| are size(v) and n-size(v).

Following these steps lead to linear time agorithm, with the following high level pseudo code.

Choose arbitrary r
Calculate size(u) for all nodes
sum = 0
for each edge (u,v) do:
  sum = sum + (cost(u,v) * (size(v) * (n-size(v))))
return sum

Upvotes: 0

Related Questions