给定有一条负边（u，v）的有向加权图，求最短路径（s，t）
给定：有向加权图G（V，E）和s，t是V的顶点，除边（u，V）为负外，所有边均为正。
问题：找到从s到t的最短路径（意思是：重量最小）。
我的解决方案是：因为我们有一个负优势，我们应该使用贝尔曼·福特的算法。在边缘执行n-1“松弛”，如果在n的第次迭代中出现问题，则有一个循环-因此返回false。否则，返回从s到t的最短路径。
另一个解决方案：使用Dijkstra，通过保存d（u）和传递负边（u，v）并执行“松弛”来稍微改变它，然后我们在没有负边的所有边上再次进行，如果距离改变，我们有一个循环，否则都很好并返回最短路径。
注意：我显然不确定我的解决方案，有一个负边的事实很棘手，有什么想法吗？
注2：为了使其有趣，您不能使用Bellman-Ford。
共有1个答案
您可以使用存在单个负边缘的信息来创建有效的算法。
让我们将负边的源节点表示为a，将目标节点表示为b，因此我们有负边a-
从节点s到节点t有两种路径：
边缘a-
我们打算找到从s到t的最短路径，我们将通过找到上述两种类型的最短路径来实现。
通过简单地将Dijkstra算法应用于移除负边的修改图，可以找到沿（1）类图的最小路径。
对于类型（2），我们现在对包含边a-的从s到t的最短路径感兴趣
如果图中没有负循环，那么边a-
在这种情况下（没有负循环），我们可以应用Dijkstra的算法两次，首先找到从s到a的最短路径；然后找到从b到t的最短路径。在这两种情况下，Dijkstra的算法应该应用于通过去除负边a-而修改的图
关于负周期。如果存在负循环，即在同一节点中开始和结束且成本为负的路径，且该节点位于从s到t的路径上，则从s到t的最短路径不存在。实际上，在这种情况下，通过多次包含负成本周期，从s到t的成本可以任意小。
然而，可以再次使用Dijkstra的算法来确定在图中是否存在这样的循环。注意，因为有一个单一的负边，a-
-
在一个加权有向图中，我需要找到两个结点s，t之间的最短路径。以下是限制： 权重可以为负值。 路径必须经过一个特定的边，让我们从节点u到V调用her e和shes。 输出路径必须简单，即我们只通过一个节点一次。 因为我希望它最短，所以我将检查在从s到u之前从v到t运行bellman ford是否比相反的方式更快（如果有节点，两个节点都使用where是放置它的最佳位置）。 谢谢你的帮助！
-
给出了一个图G=(V，E)，它是正加权的，有向的，无圈的。我设计了一个在O(k(m+n))中运行的算法，用于报告从s到T的k-边最短路径。k-边最短路径定义为从s到t的具有k条边的路径，并且对于从s到t的所有路径，该路径的总权也必须是最小的。 由于BFS不能单独用于寻找最短路径（除非权重相等），我认为运行时间意味着使用BFS寻找具有k条边的路径。让我感到困惑的是k，因为我认为它意味着表演BFS k
-
我有一个有向加权图
-
给出一个无向加权图G和两个顶点：开始顶点和结束顶点 什么是最有效的算法，找到从开始到结束的最短路径，并能够将恰好一条边的权重变为零？ 编辑：我知道dijkstra算法，但正如我所说，在这个问题中情况不同：我们可以将一条边变为零，
-
我试图解决的问题是： 给出一个图，其中每个边都用红色或蓝色着色： a）给出了生成两顶点(s，t)之间经过最小数量红边的路径的算法。
-
我有一个有圈的有向图。所有边都是加权的，权重可以是负值。可能会有负循环。