我有一个 DAG (每个边的成本/权重)，想要找到两组节点之间的最长路径。与图中的节点总数相比，两组起始节点和目标节点是不相交的，并且大小较小。
我知道如何在一个起始节点和目标节点之间高效地执行此操作。有了多个，我可以列出从每个起点到每个目标节点的所有路径，并选择最长的路径-但这需要二次搜索单个路径。有没有更好的办法？
最佳答案
我假设您想要的最长路径可能从第一个集合的任何节点开始，到第二个集合的任何节点结束。然后，您可以添加两个虚拟节点:
所有新添加的边缘的权重应为零。
该图仍将是DAG。现在，如果您使用标准算法在DAG中找到两个新节点之间的最长路径，则将获得从第一个集合开始到第二个集合结束的最长路径，除了会有一个额外的零-加权边缘在开始时，额外的零加权边缘在末尾。
顺便说一句，该解决方案本质上是从第一组的所有节点执行算法，但是与您的问题建议的顺序方法相反，它是并行的。
关于graph - 如何在具有一组起点和目标点的图形中找到最长的路径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29405534/