Geek Answers Handbook

How to find the shortest simple path in a tree in linear time?

Here is the problem from the book of Vazirani Algorithms

The input to this problem is a tree T with integer weights on the edges. Weights can be negative, zero or positive. Give a linear time algorithm to find the shortest simple path in T. The length of the path is the sum of the weights of the edges in the path. The path is simple if no vertex is repeated. Note that the endpoints of the path are not limited.

TIP: This is very similar to the problem of finding the largest independent set in a tree.

How can I solve this problem in linear time?

Here is my algorithm, but I wonder if this is linear time, since it is no different from depth:

  • Trace tree (in depth)
  • Save indexes (nodes)
  • add values
  • do (1) to the end of the tree
  • compare the amount and print the path and amount

this problem is similar to this topic, but there is no definite answer.

+6
algorithm graph dynamic-programming graph-theory graph-algorithm
source share
1 answer

This problem is largely equivalent to the problem of the minimum sum of a subsequence and can be solved in a similar way using dynamic programming.

We will calculate the following arrays using a DF search:

dw1[i] = minimum sum achievable by only using node i and its descendants. pw1[i] = predecessor of node i in the path found for dw1[i]. dw2[i] = second minimum sum achevable by only using node i and its descendants, a path that is edge-disjoint relative to the path found for dw1[i].

If you can compute them, take min(dw1[k], dw1[k] + dw2[k]) over all k . This is because your path will take one of the following main forms:

  kk | or / \ | / \ |

All of them are covered by the amounts that we accept.

Dw1 calculation

Run DFS from the root of the node. In DFS, keep track of the current node and its father. In each node, suppose its children are d1, d2, ... dk . Then dw1[i] = min(min{dw1[d1] + cost[i, d1], dw1[d2] + cost[i, d2], ..., dw1[dk] + cost[i, dk]}, min{cost[i, dk]}) . Set dw1[i] = 0 for leaf nodes. Remember to update pw1[i] with the selected predecessor.

Dw2 calculation

Run DFS from the root of the node. Do the same as you did for dw1 , except when switching from node i to one of your children k , update dw2[i] if pw1[i] != k However, you call the function recursively for all children. In pseudocode, it will look something like this:

 df(node, father) dw2[node] = inf for all children k of node df(k, node) if pw1[node] != k dw2[node] = min(dw2[node], dw1[k] + cost[node, k], cost[node, k])
+6
source share

More articles:


All Articles