CODEWITHSUNDEEP
algorithm
Felipe
Felipe

Reputation: 697

All pairs shortest path in a connected graph with N nodes and N-1 edges

I have a graph with N nodes (2 <= N <= 50000) and N is even. The values of the Nodes are always a number between 1 and N/2. It's granted that there is only one path between any pair of nodes and the weight of the edges is always one. How can i sum the distance of all nodes with equal value ?

This is a example:

The number inside the square is the value of the node and the small number below it its the identification of the node.

Graph

In this example the sum is distance(1,6) + distance(2,5) + distance(3,4) = 5

Floyd-Marshall or simple BFS its to expensive for this case. I've seen that on DAGs is possible to get the shortest path with a topological sort. In this case it is a good approach ?

Upvotes: 2

Views: 781

Answers (1)

Niklas B.
Niklas B.

Reputation: 95328

I'm assuming here that you have a disjoint partition of your node set into pairs, represented by numbers from 1 to N/2. I'm also assuming that by "there is only one path between any pair of nodes" you really mean any pair and not just those of the same color.

In that case, first realize that your graph is a tree. So root it arbitrarily, and traverse it in depth-first order to compute the depth of all nodes. Note that for two nodes x and y, if their lowest common ancestor is l, then 

distance(x, y) = distance(x, l) + distance(y, l) 
               = depth(x) - depth(l) + depth(y) - depth(l) 
               = depth(x) + depth(y) - 2*depth(l)

You can use Tarjan's off-line LCA algorithm to compute the LCA of all your pairs in (almost) linear time and compute the distances. You don't even need to store the LCAs in this case.

Runtime: O(n * α(n)) with naive disjoint set union, O(n) with the improvements from "A Linear-Time Algorithm for a Special Case of Disjoint Set Union", Gabow & Tarjan, 1983

Upvotes: 2

Related Questions