algorithm - 阻止仙人掌图上的有向路径

Question

我想在具有某些阻塞定向路径的仙人掌图上找到最长的路径距离。

例如，如果我们有以下 4 个节点，

这将意味着

• 如果我们访问 1，我们不能去 2，即 1 -> 2 和 1 -> 3 -> 2 是不允许的。但是，2 -> 1 是允许的。

同样地

• 不能从 2 到 3

• 不能从 3 到 1

• 不能从 1 到 0

• 可以旅行任何其他人

所以我们有路径 (1, 3, 2), (0, 2, 1) 等等。因此最长的距离是 3。

在这种情况下，答案是 9。（4、5、6、7、8、0、9、2、3）等...

我被困在这个问题上一个星期。不过，我不知道如何接近。谢谢。

Answer 1

听起来你所拥有的只是一个有向图，但与箭头指示的方向相反。反转方向并运行标准最长路径图算法。

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

据我了解，允许的路径是（但你不能走其他路）：

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

将它们转换为有向图并在其上运行最长路径算法。

编辑：更新答案以反映最长路径而不是最短路径