How to find longest path in graph?

6
votes

We are given an Adjacency list of the form

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

(U,V,C) means there's an edge from U to V with cost C.

The given Adjacency list is for a single connected tree with N nodes thus containing N-1 edges.

A set of nodes F=F1,F2,F3...Fk are given.

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

Is DFS from each node in F the only option?

2
algorithmdata-structuresgraphtreedepth-first-search
Does DFS = Depth First Search? - Pieter Geerkens
You appear o be asking for the longest path comprised ONLY of nodes in F, which would of necessity have to have a length == k-1 and a cost SUM(C from (Fi,Fi-1,C)) over F for a to-be-determined ordering of F. Doesn't this reduce to a generalization of Euler's Konigsberg Bridges problem? - Pieter Geerkens
Also, perhaps this belongs on Math SE instead of here. - Pieter Geerkens
If every node has at most one successor, it's trivial in O(n^2). - John Dvorak
If it's a general graph, then finding the longest path is NP-complete and equivalent to the hamiltonian path problem. - John Dvorak

2 Answers

1
votes

I understood your question as asking to find a pair of nodes from the set F so that the unique path between those two nodes is as long as it can be. The path is unique because your graph is a tree.

The problem can be solved trivially by doing DFS from every node in F as you mention, for an O(n k) solution where n is the size of the graph and k is the size of the set F.

However, you can solve it potentially faster by a divide and conquer approach. Pick any node R from the graph, and use a single DFS to tabulate distances Dist(R, a) to every other node a a and at the same time partition the nodes to subtrees S1,...,Sm where m is the number of edges from R; that is, these are the m trees hanging at the root R. Now, for any f and g that belong to different subtrees it holds that the path between them has Dist(R, f) + Dist(R, g) edges, so it is possible to search for the longest such path in O(k^2) time. In addition, you have then to recurse to the subproblems S1,...,Sm to cover the case where the longest path is inside one of those trees. The overall complexity can be lower than O(n k) but the math is left as an exercise to the reader.

-2
votes

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

You can find the path in just 2 complete traversal i.e., O(2N) ~ O(N) for large value of N.

you should do below step.

  1. Pick any node in the spanning tree.
  2. Run any algo (DFS or BFS) from the node and find the longest cost path from this node.

This will not be your longest cost path as you started by randomly picking a node.

  1. Run BFS or DFS one more time from the last node of longest cost path found at step 2.
  2. This time the longest cost path you get, will be the Longest cost path in spanning tree.

You do not have to run DFS from each node.