graph - 带约束的有向无环加权图的遍历

Question

我有一个要遍历的有向无环加权图。

有效解决方案路径的约束是：

1. 考虑到第二个约束，路径中遍历的所有边的权重之和必须是图中可能的最高值。
2. 在所选路线中必须访问过恰好 N 个顶点（包括开始和结束顶点）。

通常，该图将具有大量顶点和边，因此尝试所有可能性不是一种选择，并且需要相当有效的算法。

为这个问题寻找一些指针或合适的算法。我知道使用 Dijkstra 算法很容易满足第一个条件，但我不确定如何结合第二个条件，甚至不知道从哪里开始寻找。

如果需要任何其他信息，请告诉我。

Answer 1

我不确定您是否对图中任何长度为N的路径感兴趣，或者只是对两个特定顶点之间的路径感兴趣；我怀疑后者，但你没有在你的问题中提到这个限制。

如果是前者，解决方案应该是一个简单的类似 Dijkstra 的算法，您可以通过它们的潜在路径值对所有边缘进行排序，该路径值从边缘权重开始，并通过已构建的相邻路径进行调整。在每次迭代中，获取具有最佳潜在路径值的节点并将其添加到相邻路径中。当您获得长度为 N 的路径（或在两侧截断的更长）时停止。还有一些其他的技术细节，尤其是。wrt。创建长路径，但我不会详细说明，因为我怀疑这不是您感兴趣的。:-)

如果您有固定的源和接收器，我认为不涉及深层魔法 - 只需运行一个基本的 Dijkstra，其中路径将与添加到队列中的每个顶点相关联，但不要将路径长度 >= N 的顶点插入队列并且不要将 sink 插入到队列中，除非它的路径长度为 N。