graph - 在图中找到最长的路径，其中每个节点最多有两条传入边和两条传出边

Question

正如标题所说，我必须在有向图中找到最长的路径，其中每个节点最多有两个传入边和两个传出边。我不知道这个事实是否有帮助。该图最多有 10000 个节点。我需要找到从节点 0 到节点“退出”的最长路径，即 10001。

我尝试编写 dijkstra 代码，但没有成功。

提前致谢。

Answer 1

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