Shortest Path in a Graph visiting all nodes atleast once!

I have been trying to solve following problem from topcoder practice problems:

Problem Link

I have found one of topcoder user’s solution, but I could not understand it. Can somebody please explain me the concept used in code.

public class PowerOutage {
public int estmateTimeOut (int[] fromJunction, int[] toJunction, int[] ductLength) {
	int result = -maxDuctLength (fromJunction, toJunction, ductLength, 0);
	for (int i = 0; i < fromJunction.length; i++) {
		result += 2 * ductLength[i];
	}
	return result;
}

public int maxDuctLength (int[] fromJunction, int[] toJunction, int[] ductLength, int ductNumber) {
	int result = 0;
	for (int i = 0; i < fromJunction.length; i++) {
		if (ductNumber == fromJunction[i]) {
		 result = Math.max(result, ductLength[i] + maxDuctLength(fromJunction,toJunction,ductLength,toJunction[i]));
		}
	}
	return result;
}

}

1 Like

First, consider a tour on a tree that visits each node exactly once and returns to the starting node. We claim the minimum cost of such a tour is 2 times the sum of all the edges in the tree. To see this, we can use inductive reasoning. Clearly, for a one-node tree this is trivially true (the sum of all the edges is zero). Now, suppose we have an arbitrary rooted tree. Then, we know that there is at least one child, so for each child, we must travel the edge from the root to the child. We can then take the tour of the child’s subtree (which is at least 2 times the sum of its edges), but then we need to travel the edge back to the root. We do this for each child, so we can see that the total cost of the tour is at least 2 times the total sum of the edges.

Now, the problem is saying that we do not have to return to the root after we visit all the nodes. Suppose we stop at a node different from the root. Since a closed tour has minimal cost 2 times the sum of edges, a tour that starts at the root and ends and a different node will have cost at most 2 times the sum of the edges - the length of the path from the root to node. Thus, that is what “maxDuctLength” is calculating, so we subtract that from our overall answer.

Hope that clears it up.

5 Likes

[this is not an answer but a follow-up doubt or question]

if suppose dijkstra was used for computing maxDuctLength , would it had been more efficient than the solution given , if yes then will it be significant? if not does that mean dijkstra is not that important for tree and ad-hoc implementations are as good and efficient as we can be?

It would have been certainly more efficient if we had used adjacency lists for each node which will essentially eradicate need of looping over all edge relations and checking if (ductNumber == fromJunction[i]). So let us suppose we are not that concerned with that implementation part.

Problem seems interesting :slight_smile:

Somebody please reply…:frowning: