2

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, enter image description here

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

enter image description here

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

ZeroPepsi
  • 141
  • 3

1 Answers1

0

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

Nuclearman
  • 5,029
  • 1
  • 19
  • 35
  • Dijkstra’s algorithm will give back the *shortest* paths. The OP wants the longest path. – templatetypedef Sep 10 '20 at 03:31
  • @templatetypedef Ah yes, good catch, missed that for some reason. Point remains, a standard longest path algorithm should work once the graph is converted into a directed graph. Will update the answer though. – Nuclearman Sep 10 '20 at 21:55