具有负长度周期的有向图中的最短路径

Question

是否有一种算法用于在有向图中找到最短路径，其中包括负长度的周期？约束是每个节点只能访问一次，因此存在解决方案。

我知道Bellman-Ford算法，但是当存在负循环时它会失败。同样清楚的是，遍历负循环永远会使问题定义不明确，所以我限制了最多访问每个节点一次的路径。

有这样的算法吗？我可以使用现成的实现吗？

- -编辑 - -

如下所述，这是实际应用：

给定包含手写的输入图像，我可以估计每个像素的笔划方向的概率：

然后，我可以将像素放入图形中，并找到笔的路径：

看看“l”是如何被遗漏的？如果我可以将相邻权重设置为负数，则最佳路径将遍历所有字母。但负重会产生负循环。

Answer 1

你是对的，贝尔曼 - 福特算法在这种情况下失败了。你可以参考this resource的第2部分。它讨论了无向图的问题，并基于Edmonds的最小权重完美匹配算法。事实上，您可能对this question感兴趣，这与您的非常相似。

当图形是有向图形时，然后正如@SaiBot指出的那样，问题减少到NP Hard问题，并且没有可能的有效解决方案。