Blocking directed paths on a Cactus Graph

Question

I want to find the longest path distance on a cactus graph with certain blocking directed paths.

For example, if we have following 4 nodes,

This would mean that

• if we visit 1, we cannot go to 2 That is, 1 -> 2 and 1 -> 3 -> 2 are not allowed. However, 2 -> 1 is allowed.

Likewise

• cannot travel from 2 to 3

• cannot travel from 3 to 1

• cannot travel from 1 to 0

• can travel any others

So we have the paths (1, 3, 2), (0, 2, 1), etc.. Therefore the longest distance is 3.

In this case, the answer is 9. (4, 5, 6, 7, 8, 0, 9, 2, 3), etc...

I’m stuck on this problem one week. Still, I have no idea how to approach. Thanks.

Answer 1

Sounds like what you have is just a directed graph, but in the opposite direction as the arrows indicate. Invert the directions and run a standard longest path graph algorithm.

https://en.wikipedia.org/wiki/Longest_path_problem

As I understand it the allowed paths are (but you can't go the other way):

0 => 1
1 => 3
3 => 2
2 => 1

Convert those into a directed graph and run a longest path algorithm on it.

Edit: Updated answer to reflect longest path rather than shortest path