考虑可能有负周期的有向图G =（V，A，W）上的最短路径问题。我们仅考虑简单路径，即没有重复顶点的路径。通过构造一个新图G'（V，A，W'），使G'和G具有相同的顶点和弧，但是对于每个弧，其在G'中的权重比在G中的权重高一个常数。 >
很明显，如果P1和P2是两条路径，并且G中的w（P1） 此外，the shortest path problem with negative cycles is actually NP-hard。如果我是对的，并且我们可以将负循环的情况减少到没有负循环的情况，那么问题不应该是多项式吗？ 我想我缺少了一些东西，但是我不确定是什么。
考虑可能有负周期的有向图G =（V，A，W）上的最短路径问题。我们仅考虑简单路径，即没有重复顶点的路径。通过构造一个新图G'（V，A，W'）...
很明显，如果P 1