如何在具有一组起点和目标点的图中找到最长的路径？
How to find the longest path in a graph with a set of start and target points?
我有一个 DAG（每条边 costs/weights），我想找到两组节点之间的最长路径。与图中的节点总数相比，两组起始节点和目标节点不相交且规模较小。
我知道如何在 一个 开始和目标节点之间高效地执行此操作。有了多个，我可以列出从每个起点到每个目标节点的所有路径并选择最长的一个——但这需要二次方的单路径搜索。有没有更好的方法？
我假设您想要最长的路径，它从第一组的任何节点开始，到第二组的任何节点结束。然后可以添加两个虚拟节点:
第一个节点没有前任节点，其后继节点是第一组中的节点。
第二个节点没有后继，其前任是第二组的节点。
所有新添加的边都应该具有零权重。
该图仍然是 DAG。现在，如果您使用标准算法在两个新节点之间找到 DAG 中的最长路径，您将获得从第一组开始到第二组结束的最长路径，除了会有一个额外的零 -开头有加权边，结尾有额外的零加权边。
顺便说一下，这个解决方案本质上是从第一组的所有节点执行算法，但是并行执行而不是你的问题建议的顺序方法。
我有一个 DAG（每条边 costs/weights），我想找到两组节点之间的最长路径。与图中的节点总数相比，两组起始节点和目标节点不相交且规模较小。
我知道如何在 一个 开始和目标节点之间高效地执行此操作。有了多个，我可以列出从每个起点到每个目标节点的所有路径并选择最长的一个——但这需要二次方的单路径搜索。有没有更好的方法？
我假设您想要最长的路径，它从第一组的任何节点开始，到第二组的任何节点结束。然后可以添加两个虚拟节点:
第一个节点没有前任节点，其后继节点是第一组中的节点。
第二个节点没有后继，其前任是第二组的节点。
所有新添加的边都应该具有零权重。
该图仍然是 DAG。现在，如果您使用标准算法在两个新节点之间找到 DAG 中的最长路径，您将获得从第一组开始到第二组结束的最长路径，除了会有一个额外的零 -开头有加权边，结尾有额外的零加权边。
顺便说一下，这个解决方案本质上是从第一组的所有节点执行算法，但是并行执行而不是你的问题建议的顺序方法。