给定有一个负边 (u,v) 的有向加权图，找到最短路径 (s,t)
Given directed weighted graph that has one negeative edge (u,v), find shortest path (s,t)
给定： 有向加权图 G(V,E) 和 s,t 是 V 的顶点，除了边 (u,v) 这是负数。
问题：找到从s到t的最短路径（含义：权重最小）
我的解决方案： 好吧，因为我们有负边，所以我们应该使用 Bellman-Ford 算法。在边上执行 n-1 "relax"，如果在第 n 次迭代中出现问题，则存在一个循环 - 因此 return 错误。否则，return 是从 s 到 t 的最短路径。
另一个解决方案： 使用 Dijkstra，并通过保存 d(u) 并传递下降沿 (u,v) 并执行 "relax" 来稍微改变它，然后我们在没有负边的所有边上再次进行，如果距离改变了，我们就有了一个循环，否则一切都很好，return 最短路径。
注意：我显然不确定我的解决方案，事实上有一个负边缘是棘手的，有什么想法吗？
注意 2：为了让它变得有趣，您不能使用 Bellman-Ford。
您可以使用存在 单个 下降沿的信息来创建高效算法。
让我们将负边的源节点表示为a，将目标节点表示为b，因此我们有负边a -> b。
从节点s到节点t有两种路径：
- 边
a->b 不是路径的一部分；
- 边
a->b 是路径的一部分。
我们打算找到从s到t的最短路径，我们将通过找到上述两种类型中的每一种的最短路径来实现。
沿着类型 (1) 的最小路径可以通过简单地在去除负边的修改图上应用 Dijkstra 算法来找到。
对于类型 (2)，我们现在感兴趣的是从 s 到 t 且包含边 a->b 的最短路径。此路径必须采用以下形式：s -> ... -> a -> b -> ... -> t.
如果图中没有负循环，则边 a->b 应该只在最短路径中出现一次（有关负循环的讨论，请参阅本答案的最后部分）。
在这种情况下（没有负循环），我们可以应用Dijkstra的算法两次，首先找到从s到a的最短路径；然后找到从 b 到 t 的最短路径。在这两种情况下，Dijkstra 算法都应应用于通过移除负边 a->b.
修改的图
关于负循环。如果存在负循环，即一条路径开始和结束于同一个节点并且具有负成本，并且该节点在从s到[=14的路径上=]，那么从s到t的最短路径不存在。实际上，在这种情况下，通过多次包含负成本循环，可以使从 s 到 t 的成本任意小。
但是，再次使用Dijkstra 算法可以确定图中是否存在这样的循环。请注意，由于有一个负边沿 a->b，负循环需要包含它。因此我们需要有一条从b到a的路径，其总成本小于a->b的权重的绝对值。我们可以通过应用Dijkstra 算法来检查是否存在这样一条路径，起始节点b 和目的地a。同样，Dijkstra 的算法应该应用于删除了 a->b 边的图（我们对将它放在路径中不感兴趣），因此所有边权重都是正的。
给定： 有向加权图 G(V,E) 和 s,t 是 V 的顶点，除了边 (u,v) 这是负数。
问题：找到从s到t的最短路径（含义：权重最小）
我的解决方案： 好吧，因为我们有负边，所以我们应该使用 Bellman-Ford 算法。在边上执行 n-1 "relax"，如果在第 n 次迭代中出现问题，则存在一个循环 - 因此 return 错误。否则，return 是从 s 到 t 的最短路径。
另一个解决方案： 使用 Dijkstra，并通过保存 d(u) 并传递下降沿 (u,v) 并执行 "relax" 来稍微改变它，然后我们在没有负边的所有边上再次进行，如果距离改变了，我们就有了一个循环，否则一切都很好，return 最短路径。
注意：我显然不确定我的解决方案，事实上有一个负边缘是棘手的，有什么想法吗？
注意 2：为了让它变得有趣，您不能使用 Bellman-Ford。
您可以使用存在 单个 下降沿的信息来创建高效算法。
让我们将负边的源节点表示为a，将目标节点表示为b，因此我们有负边a -> b。
从节点s到节点t有两种路径：
- 边
a->b不是路径的一部分； - 边
a->b是路径的一部分。
我们打算找到从s到t的最短路径，我们将通过找到上述两种类型中的每一种的最短路径来实现。
沿着类型 (1) 的最小路径可以通过简单地在去除负边的修改图上应用 Dijkstra 算法来找到。
对于类型 (2)，我们现在感兴趣的是从 s 到 t 且包含边 a->b 的最短路径。此路径必须采用以下形式：s -> ... -> a -> b -> ... -> t.
如果图中没有负循环，则边 a->b 应该只在最短路径中出现一次（有关负循环的讨论，请参阅本答案的最后部分）。
在这种情况下（没有负循环），我们可以应用Dijkstra的算法两次，首先找到从s到a的最短路径；然后找到从 b 到 t 的最短路径。在这两种情况下，Dijkstra 算法都应应用于通过移除负边 a->b.
关于负循环。如果存在负循环，即一条路径开始和结束于同一个节点并且具有负成本，并且该节点在从s到[=14的路径上=]，那么从s到t的最短路径不存在。实际上，在这种情况下，通过多次包含负成本循环，可以使从 s 到 t 的成本任意小。
但是，再次使用Dijkstra 算法可以确定图中是否存在这样的循环。请注意，由于有一个负边沿 a->b，负循环需要包含它。因此我们需要有一条从b到a的路径，其总成本小于a->b的权重的绝对值。我们可以通过应用Dijkstra 算法来检查是否存在这样一条路径，起始节点b 和目的地a。同样，Dijkstra 的算法应该应用于删除了 a->b 边的图（我们对将它放在路径中不感兴趣），因此所有边权重都是正的。