我最近一直在研究所有对最短路径算法，比如弗洛伊德-瓦赫尔和约翰逊的算法，我注意到这些算法产生了正确的解，即使一个图包含负权边(但不包含负权环)。作为比较，Dijkstra的算法(它是单源最短路径)不适用于负重边。是什么使全对最短路径算法在负权重的情况下工作？
浏览 9提问于2014-04-06得票数 6
回答已采纳
2回答
Dijkstra的最短路径算法会在具有负权边的有向树上返回正确的结果吗？
在具有负权重的一般图上，该算法将失败，但由于它是一棵有向树，因此感觉该算法会成功。
浏览 5提问于2022-06-01得票数 2
1回答
对线性时间中的混合图(即有向和无向边或无向边表示为两条有向边)中的单对最短路问题，是否有一种算法，具有负、实边权和非负圈。只提到了问题的单源和全对变体的算法.我知道，这些问题中的一个也解决了单对问题，但没有一个在线性时间内工作，而且所有的准则都是这样。
那么，对于具有上述条件的单对最短路径问题，是否存在线性时间算法呢？
浏览 2提问于2015-03-16得票数 0
4回答
首先，让我们定义算法：我想知道如何使用Dijkstra算法将最短路径形式s保存到t。我在谷歌上搜索，但找不到任何特别的东西；我也改变了Dijkstra算法，但我无法得到任何答案。如何使用Dijkstra保存从s到t的最短路径？
浏览 6提问于2015-03-11得票数 11
回答已采纳
在Bellman算法()的塞奇威克和韦恩实现中，findNegativeCycle使用EdgeWeightedDirectedCycle ()在最短路径树( edgeTo数组中的边缘)中寻找有向循环。问题：如果最短路径树同时包含零权循环和负权循环，那么如何确保EdgeWeightedDirectedCycle不返回零权循环(从而导致断言失败)？
浏览 2提问于2020-11-26得票数 4
我目前正在研究非负边权图中的最短路径问题。我知道Dijkstra算法可以给出单源最短路径问题的解决方案，也就是可以找到从一个节点到所有其他节点的最短路径，但是我还没有找到算法，可以给我一个先验的更简单的问题:找到两个节点之间的最短路径。直觉上，我认为可以找到例子，表明“简单”问题并不比单源最短路径问题更简单，但我正在寻找参考资料，在简单的图(即有几个节点)上显示这种矛盾(先验)。
浏览 4提问于2022-05-11得票数 2
1回答
Dijkstra的算法比bellman算法更有效，但是我们仍然使用bellman算法来表示负边，但是这些负边在网络中代表什么呢？
浏览 4提问于2013-10-25得票数 0
回答已采纳
1回答
加权无向图上的最长路径
、、、
我已经实现了一种使用Dijkstra算法寻找最短路径的方法。是否可以修改该方法以找到最长的路径？如果我把所有的重量都减了，这难道不管用吗。我当前图表上的所有权重都是正数。此外，不应该有重复的路径。我知道Bellman Ford算法在负权值下工作，但我希望我能修改我现有的最短路径法。
浏览 5提问于2013-11-29得票数 1
回答已采纳
1回答
所以我最近一直在研究Dijkstra的算法和有向图。然而，我似乎不明白这一点，这真的开始困扰我。说明了如何修改Dijkstra的算法，以解决单源最短路径问题，如果正好有一个负权边，但没有负权循环。
到目前为止，我的最初想法是以某种方式将图分开，并分别执行算法，但这就是我所想到的全部。我想指出的是，如果负边的数目是有限的，那么基于Dijkstra的算法可能会做得更好。例如，如果从u到v只有一个负
浏览 3提问于2015-04-29得票数 2
回答已采纳
设G是一个无负圈的有向加权图，设计了一种算法，以求G中的最小权圈，其时间复杂度为O({x}V}^3)。我在这个问题上走在正确的轨道上吗？是否有可能修改弗洛伊德-沃尔算法，以求图中
浏览 1提问于2014-03-30得票数 3
回答已采纳
1回答
给出了边权为整数(正、零或负)的n个顶点加权有向图，确定是否有任意大权的路径可以在时间-中执行。O(n)O(n^1.5)而不是O(nlogn)O(2n)但不是O(n^3)
我不知道用什么算法来寻找最长的路径是一个NP
浏览 1提问于2018-05-29得票数 0
回答已采纳
1回答
我想弄明白为什么有人更喜欢弗洛伊德-沃夏尔而不是迪克斯特拉：弗洛伊德-沃夏尔做了一个完整的名单和过滤器在那里。还是有其他原因我没有想到这里？
请注意:我正在处理的图是“典型”图，其中车辆需要从一个地方到另一个地方，边的权重等于顶点之间的距离(这是我所走过的点)。边可能是定向的，
浏览 0提问于2023-01-20得票数 1
回答已采纳
考虑以下策略，将具有负边权的图转换为没有负边权的图。设图中的最大幅值负边权为-k。然后，对于具有权重w的图中的每个边，将权重更新为w+k+1。为了解决原图中的最短路径问题，我们可以在修改后的图上运行Dijkstra算法，减去增加的权重，得到原图。这一说法对所有图都是正确的。
对于连通无圈图，这一说法是正确的。
浏览 0提问于2017-02-20得票数 0
回答已采纳
1回答
我有一个加权DAG，有一些负的边权，并希望找到所有的最短路径在其中。有比O(n^2)更复杂的算法吗？(我的图是完全的，即对于{1.n}和i<j中的任意i，j都有一个边(i，j) )。
谢谢
浏览 5提问于2012-08-14得票数 1
5回答
我有一个问题：“有一个可跳边的最短路径。给定一个边加权有向图，设计一个E*log(V)算法来找到从s到t的最短路径，在这里你可以将任何一个边的权重改变为零。假设边权值是非负的。”我认为我可以将任何最短路径中的任何边改变为零，而且它仍然是最短的。
浏览 7提问于2013-04-30得票数 8
回答已采纳
2回答
在有向无环图(DAG)上运行最短路径算法(通过使用回忆录的动态规划)具有运行时复杂度为O(V + E)的特性，可以使用以下公式进行验证：现在，Dijkstra的算法也要求有向图。该算法的运行时复杂度为O(E + V.log(V))，使用最小优先级队列，这显然比回忆录版本的DP慢。
这是对无界非负权的任意有向图的最快速的单源最短路径算法</
浏览 4提问于2015-01-26得票数 2
回答已采纳
2回答
运行Johnson算法后的回溯
、、、、
在图上运行之后，是否有可能知道它以前是否有负循环？为什么？
Johnson算法是一种能够计算图上最短路径的方法。这是能够处理负重的边缘，只要不存在一个循环负重。该算法由(来自)组成：
其次，使用Bellman算法，从新的顶点q开始，为每个顶点v找到从q到v的路径的最小权重h(v)。如果此步骤检测到负循环，则终止该算法。接下来，用Bellma
浏览 0提问于2018-09-04得票数 1
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
腾讯会议
云直播
对象存储活动推荐
腾讯云开发者
