How to find the longest simple path (including all intermediate nodes) in a directed cyclic graph?

Question

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.

Answer 1

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).

Answer 2

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