如何找到经过特定源节点的最负权重循环的路径？

Question

我试图找到图G中最负循环的路径，它从指定的源节点S开始和结束。

我研究了Bellman-Ford算法（以下称为“Huang算法”）的应用/扩展，该算法描述了如何找到从指定节点可到达的负循环。然而，这并不能确保从S开始的“全周期”-

以下是我目前对此主题的研究：

在Bellman-Ford算法的第n次迭代中，如果一条边可以松弛，则该图包含一个负循环。使用Huang算法，我可以通过前置字典追溯负循环的路径，直到顶点重复。当一个顶点重复时，我停止在前一个顶点上迭代，现在有了负循环的路径。但是，源顶点通常不在此路径中。我相信这有时也不是最负权重的路径。

我想找出S是其中最负循环的一部分。（这可以包括具有由黄算法检测的子周期的周期）

Answer 1

根据你的定义，你所问的可能是NP完全。如果你拿一个没有权重的图，给每个边赋予权重-1，那么你想要选择的任何节点上的最负的圈，如果该圈是哈密顿路径，那么它将具有最负的可能值，因此你有一种方法可以找到哈密顿路径是否存在，这解决了一个NP完全问题。（这假设循环不能多次使用同一顶点，但如果使用可以重复顶点的定义，则可能允许无限长的路径不断循环）。