0

Let's say we have a directed cyclic graph where every node has an edge going to exactly two other nodes - except for a 'final node', which just has multiple things going into it and nothing coming out.

Given a source, I want to find the longest possible path to that final node that doesn't hit a node more than once. There are algorithms out there to do this, but the only problem is that my graph has many different cycles, some of which are inside each other, and most naive algorithms get stuck in infinite loops when evaluated.

I tried collapsing all strongly connected components (of which there is only one), however if the source I want is inside that component, the algorithm doesn't work. And it doesn't work in the general case either, because within that strongly connected component, to hit every node you may have to hit some nodes multiple times, which I don't want.

What's an efficient algorithm I can use for calculating the longest path back to the final vertex in an unweighted directed, cyclic graph such that no node is hit multiple times?

Nico A
  • 227
  • 1
  • 14
  • Do you have sample i/o or test cases to work with? If your graph has cycles, store visited nodes in a hash or add a `visited` property to the node class. – ggorlen Jul 29 '18 at 18:25
  • 3
    Possible duplicate of [How do find the longest path in a cyclic Graph between two nodes?](https://stackoverflow.com/questions/2679081/how-do-find-the-longest-path-in-a-cyclic-graph-between-two-nodes) – ggorlen Jul 29 '18 at 18:30

1 Answers1

1

You can see this question, it's also a problem about finding the longest path in a directed cyclic graph, and the standard code is also available.

Question:http://poj.org/problem?id=3592

Answer: https://blog.csdn.net/u013514182/article/details/42364173

user10127865
  • 21
  • 4