-2

I've searched on here for how to find the longest simple path in a directed cyclic graph (simple meaning that each node is visited only once, to avoid the path being infinite), and have came across solutions like this. All such solutions I've found however only show how to calculate the length of the longest path, not the actual nodes involved in that path.

My question is hence, how could an algorithm like that be modified so that it extracted the nodes involved in the longest path? Similar to how the Floyd-Warshall all-pairs shortest path algorithm may be modified to allow path reconstruction.

Community
  • 1
  • 1
LogicChains
  • 4,332
  • 2
  • 18
  • 27
  • 1
    The accepted answer in the question you link to can be trivially modified to record the path as well as its length. – j_random_hacker Nov 14 '14 at 14:17
  • @j_random_hacker how? Maybe it's trivial to you, but it isn't to me, hence why I asked this question. – LogicChains Nov 15 '14 at 01:28
  • 1
    When does `path` change? Whenever it does, update the list of nodes in the path as well. When does `bestPath` change? Rewrite that as an `if` statement: now, in the body of that `if` statement, you can update the list of nodes in the currently best path at the same time as you update its length. – j_random_hacker Nov 15 '14 at 02:18

2 Answers2

3

To find the actual path, all you need is to keep track of the longest distance path ( you get this path from the predecessors). The longest path of vj= the longest path among precedessors U {vj}

Here is how:

  • Do topological ordering v1 > v2 >... > vn..
  • Pick any vertex vj...
  • Let dist(vj) be the longest distance from v1 to vj. Then dist(vj)=max(dist(u1)+1,dist(u2)+1,...,dist(uk)+1) where u1,u2,...,uk are the predecessors of vj.
  • path(vj)=path(ui)U{vj} where ui is the predecessor with maximum length (i.e. the one we chose in dist(vj) ) .
  • Compute this for every vj.
  • The longest path is the maximum of dist(vj) with actual path path(vj).
Xline
  • 804
  • 5
  • 13
0

I guess the following algorithm can work to find the longest path using a depth first search. The matter in between the ** are the changes to the DFS algo.

DFS(G)
  For each u  V[G]
   {done(u)=0;
    Pre(u)=NULL;}
  Time=0;  
  For each uV[G]
   If done(u) == 0
   {**longest(u)=0**;
    DFS_VISIT(u);}

DFS_VISIT(u)
Done(u)=-1;
Discover(u)=time++;
For each v adjacent to u
If done(v)==0
    { pre(v)=u;
      **Longest(v)=longest(u)+1**;
      DFS_VISIT(v);}
Done(u)=1;
Finish(u)=time++`

After finding all longest(v), I can search for the largest value and conclude it to be the longest path. What do you think @Xline

StevieG
  • 309
  • 2
  • 5
  • 12