Geek Answers Handbook

How to find the longest path in a chart?

We are assigned a list of Adjacency forms

U -> (U,V,C) -> (U,V,C) ... U2 -> ... U3 -> ... . . etc

(U,V,C) means that the edge is from U to V with a value of C.

This Adjacency list is for a single linked tree with N nodes containing N-1 edges.

Given a set of nodes F=F1,F2,F3...Fk .

Now the question is, what is the best way to find the longest path among nodes in F? Is it possible to do this in O (N)?

Is DFS from each node in F the only option?

+6
source share
2 answers

I understood your question how to ask to find a pair of nodes from the set F, so that the only way between these two nodes is to the extent possible. The path is unique because your graph is a tree.

The problem can be solved trivially by running DFS from each node in F, as you mentioned, to solve O (nk), where n is the size of the graph and k is the size of the set F.

However, you can solve this problem faster with a separation and subjugation approach. Select any node R from the graph and use one DFS to tab the distances Dist (R, a) to all other node aa and at the same time split the nodes into subtrees S1, ..., Sm, where m is the number of edges from R; those. these are m trees hanging in the root of R. Now for any f and g belonging to different subtrees, it is satisfied that the path between them has edges Dist (R, f) + Dist (R, g), therefore, we can find the longest such path in O (k ^ 2) time. In addition, you must then relate to the subtasks S1, ..., Sm in order to cover the case when the longest path is inside one of these trees. The overall complexity may be lower than O (nk), but the math remains as an exercise for the reader.

+1
source

If I understand your question correctly, you are trying to find the longest cost path in the spanning tree.

You can find the path in just 2 full rounds, i.e. O (2N) ~ O (N) with a large value of N.

You must do below step.

  • Select any node in the spanning tree.
  • Run any algo (DFS or BFS) from node and find the longest cost path from that node.

This will not be your longest cost path when you start with an arbitrary choice of node.

  1. Start BFS or DFS again from the last node of the longest cost path found in step 2.
  2. This time, the longest cost path you get will be the longest cost path in the spanning tree.

You do not need to run DFS from each node.

-2
source

More articles:


All Articles