阻止仙人掌图上的有向路径 [英] Blocking directed paths on a Cactus Graph

问题描述

我想在仙人掌图上找到最长的路径距离定向路径.

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

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

For example, if we have following 4 nodes,

这意味着

• 如果我们访问1，我们将无法前往2 即，1→ 2和1-> 3->不允许2个. 然而，2→允许1个.

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

类似

• 不能从2行驶到3

• cannot travel from 2 to 3

不能从3行驶到1

不能从1到0行驶

可以旅行其他任何人

因此我们具有路径(1、3、2)，(0、2、1)等.因此，最长距离为3.

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

在这种情况下，答案是9.(4、5、6、7、8、0、9、2、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.

推荐答案

类似于您的声音只是一个有向图，但方向与箭头指示的方向相反.反转方向并运行标准的最长路径图算法.

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.

更新了答案，以反映最长路径而不是最短路径

Updated answer to reflect longest path rather than shortest path

这篇关于阻止仙人掌图上的有向路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！