查找图中每个节点最多有两个输入边和两个输出边的最长路径

Question

由于标题说我必须在有向图中找到最长路径，其中每个节点最多有两个输入边和两个输出边。我不知道这个事实是否有助于任何事情。图表最多有10000个节点。我需要找到从节点0到节点'Exit'的10001的最长路径。

我试图编码dijkstra，但它没有工作。

在此先感谢。

Answer 1

您可以预处理您的图形，并将边缘权重设置为非常高的值，以连接到违反规则的节点的边缘，然后使用返回最长路径的修改版本的dijkstra。