一个具有负边的图是否存在，对于这个图，Dijkstra算法可以正常工作吗？

文章/答案/技术大牛

发布

2回答

单源最长路径的图- Dijkstra

algorithm、data-structures、graph、dijkstra

好吧，我发这个问题是因为这个练习：我们可以修改Dijkstra的算法，通过将最小变为最大值来解决单源最长路径问题吗？如果是，那么证明你的算法是正确的。如果没有，则提供一个反例。对于这个练习或与Dijkstra算法相关的所有事情，，我假设在图中没有负数。否则，它就没有多大意义，因为即使对于最

浏览 6提问于2012-05-05得票数 12

回答已采纳

3回答

Dijkstra算法= SSSP

algorithm、dijkstra

据我所知，dijkstra不能与负边权重一起工作。为此，我们必须使用行李员福特。 Bellman fords可以很好地处理负边权重和负循环，否则它将返回消息“负循环存在”。但是，上面显示的这个图在dijkstra中工作得很好，即使存在负边权重。那么，如何知道何时使用

浏览 25提问于2016-08-06得票数 0

回答已采纳

1回答

computer-science、graph-theory、dijkstra

我知道，“正常”的Dijkstra算法不适用于具有负边的图，因为一旦它访问边并处理它，它的权重将不是revised.However，我很难正式证明这一点，我甚至不知道从哪里开始。

浏览 35提问于2021-06-22得票数 1

3回答

用Dijkstra算法寻找哈密顿路径？

algorithm、graph、dijkstra、shortest-path

Dijkstra算法能否找到从一个源顶点到所有其他顶点的所有最短路径，使得该路径访问一个无向对称图中的所有顶点一次且恰好一次？对称图有没有更快的算法？

浏览 1提问于2013-06-07得票数 4

回答已采纳

1回答

Dijkstra的算法不修改标记顶点的距离吗？

algorithm、graph、graph-algorithm、shortest-path、path-finding

我记得我读到，一旦Dijkstra的算法标记了一个被访问的节点，它就不会再次更新其距离。请看下面的图表：| || /该算法将访问A→B→C，E和F将被排队。但是，F将首先被选中，因为它的距离较小。然后选择E，并找到离F较短的距离。在这种情况下，不应该修改F的距离，即使它已经被标记了？

浏览 3提问于2019-11-24得票数 2

回答已采纳

2回答

关于dijkstra算法的困惑？

algorithm、graph、dijkstra、shortest-path

根据算法书Corman的说法，Dijkstra只适用于所有边都具有非负权的图。这是否意味着，如果有任何负权重的边，它将不工作的整个图？还是不算负重边？请指出哪个是对的？

浏览 0提问于2013-08-09得票数 4

1回答

我们能不能在修改后的图上运行Dijkstra算法，减去增加的权重，得到原始距离？

algorithm、data-structures、graph、shortest-path、dijkstra

考虑以下策略，将具有负边权的图转换为没有负边权的图。设图中的最大幅值负边权为-k。然后，对于具有权重w的图中的每个边，将权重更新为w+k+1。为了解决原图中的最短路径问题，我们可以在修改后的图上运行Dijkstra

浏览 0提问于2017-02-20得票数 0

回答已采纳

2回答

有向图上具有负边的Dijkstra算法

algorithm、theory

如果唯一的负边成本来自初始节点，该怎么办？这个算法还能工作吗？我觉得是，因为我想不出反例，但我很难证明这一点。有反例吗？负边对于Dijkstra来说是一个问题，因为如果有一条边可以稍后选择，并且很大程度上是负权重的，那么就不能保证你选择的边会产生最短<em

浏览 0提问于2010-10-01得票数 16

回答已采纳

1回答

BFS能被修改为搜索带负加权边的图吗？

java、breadth-first-search、weighted-graph

我编写了一个DFS算法，它在图中的顶点之间找到一条路径，但希望优化它以返回包含最小边数的路径。路径：不能多次访问任何顶点。路径的总权重必须始终为正，包括路径末端顶点之前的任何顶点的路径。权重可视为使用每

浏览 3提问于2021-07-24得票数 2

回答已采纳

2回答

最小生成树和最短路径

algorithm、graph-algorithm、shortest-path、minimum-spanning-tree

我遇到了这样一个问题：给定一个具有整数权重(正负)的连通有向图，开发一个算法来寻找两个顶点之间的最短路径。我想我可以使用最小生成树算法，例如kruskal的算法，然后使用可能的dijkstra算法来证明，因为在MST中，每个顶点只有一条进入边，dijkstra的算法

浏览 1提问于2012-11-08得票数 0

4回答

图中的最长路径

algorithm、graph、longest-path

在过去的两天里，我一直在尝试寻找一些计算图中最长路径的逻辑。我知道对于DAG我可以很容易地找到它，通常它是多项式时间algorithm.Formally。我想要实现启发式来计算最长路径，而且，如果图中存在边的概率p是给定的，我们如何解决problem..help。

浏览 1提问于2011-11-08得票数 1

1回答

dijkstra's vs Bellman-Ford算法

algorithm、graph、dijkstra、graph-traversal、bellman-ford

我目前的理解是，dijkstra的算法比贝尔曼-福特算法更有效，只是它不能处理负边缘。然而，假设我们有一个边权重图，其中有负权重的边，图中没有负权重的圈，我们还能使用dijkstra算法吗？

浏览 7提问于2019-11-28得票数 2

9回答

即使只有一个负重边，Dijkstra的算法也适用吗？

algorithm、data-structures、dijkstra

如果有向图只有一个负权边，并且不包含负权环，那么Dijkstra的算法能工作吗？

浏览 6提问于2013-11-21得票数 13

回答已采纳

2回答

我们能用dijkstra算法找到任何循环吗？

data-structures、graph-theory、dijkstra

我们能用Dijkstra的算法找到循环吗？如果我们能做什么，我们必须要做的改变吗？

浏览 5提问于2014-07-02得票数 0

回答已采纳

2回答

Dijkstra的Single Source Shortest Path算法能检测到图中的无限循环吗？

algorithm、dijkstra、shortest-path、infinite、bellman-ford

所以我来到了这个美丽的问题，它要求你写一个程序，找出在有向图中是否存在负无穷短路径。(也可以认为是查找图中是否存在“负循环”)。下面是这个问题的链接：我成功地解决了这个问题，我从图中的任何源开始，运行了两次Bellman Ford算法。第二次运行算法时，我检查节点是否可以

浏览 2提问于2013-11-21得票数 9

回答已采纳

5回答

使用Dijkstra找到最小生成树？

algorithm、language-agnostic、graph-theory、dijkstra、minimum-spanning-tree

通常用于查找图中两个节点之间的最短距离。它能用来找出最小的吗？如果是这样的话，是怎么做的？编辑:这不是家庭作业，但我正在尝试理解一个旧的练习考试中的一个问题。

浏览 5提问于2009-12-16得票数 20

回答已采纳

1回答

DAG拓扑排序图中松弛边的Dijkstra算法

algorithm、graph、graph-theory、dijkstra

我在读算法第三版的简介。解决这一问题的方法有3种。我的询问是关于其中两个人的。这是众所周知的</em

浏览 8提问于2016-05-16得票数 4

回答已采纳

2回答

Bellman算法能用于寻找只有正边的图上的最短路径吗？

algorithm、graph-algorithm、dijkstra、bellman-ford

我知道Dijkstra的算法只能用于边的正长度，Bellman算法也可以用于图的负长度。假设我们有一个只有正边的图。贝尔曼-福特会给出和迪克斯特拉一样的结果吗？

浏览 5提问于2015-06-06得票数 0

回答已采纳

1回答

为什么迪克斯特拉的算法必须在每一轮中提取最小值？

algorithm、graph、graph-algorithm、shortest-path、dijkstra

认为该图适用于Dijkstra算法，即不存在负边权。我很难说服自己，Dijkstra的算法只有选择每一轮中的最小距离节点才能工作。什么能证明除了最小距离节点外，提取任何东西都会导致Dijkstra算法的失败？我正在寻找一个好的论点，但支持的例子是受欢迎的。

浏览 2提问于2017-04-05得票数 4

回答已采纳

1回答

非加权图中最短路径的求法

algorithm、graph

在大学关于图论的课程中，我们讨论了寻找最短路径的问题，因此Dijkstra的算法出现了，在这一点上，我应该提到图的边是加权的，用weights>0。然后教授问，如果边不加权，我们如何才能找到最短的路径，我认为同样的算法可以做到，因为边缘具有“相同”的非负权重。但他建议BFS。这是真的<e

浏览 0提问于2014-10-09得票数 0

回答已采纳

点击加载更多

单源最长路径的图- Dijkstra

Dijkstra算法= SSSP