Dijkstra算法:所有最短路径都是非循环的吗？

文章/答案/技术大牛

发布

4回答

最佳最短路径算法

algorithm、shortest-path

“弗洛伊德-沃尔”算法“和”Dijkstra的算法“”之间有什么区别，哪种算法是图中最短路径的最佳选择？我需要计算网络中所有对之间的最短路径，并将结果保存到一个数组中，如下所示：A 0 10 15 5 20 B 10

浏览 20提问于2009-12-04得票数 27

回答已采纳

1回答

寻找最短周期

graph、cycle、dijkstra

基本上，我需要在一个图中有一个覆盖所有顶点并返回到源的最短路径。只要是最短路径，任何顶点的重复都是可以的。我的算法从源开始。我运行dijkstra算法来找到最短路径。然后我选择最小的加权未达顶点，并再次运行dijkstra作为所选顶点作为源，并继续运行，直到所有顶点都完成。

浏览 0提问于2012-10-30得票数 0

1回答

shortest-path、dijkstra

我知道，如果算法达到负循环，算法就不会终止，如果路径包含一个距离大于0的循环，那么它就不是最短路径。我的问题是，如果存在一个循环距离为0的最短路径会发生什么，算法会将该循环包含在最短路径中吗？你会说所有的最短路径都<em

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

2回答

关于dijkstra算法的困惑？

algorithm、graph、dijkstra、shortest-path

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

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

1回答

决定是否所有从s到t的最短路径都包含边e

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

设G= (V;E)是边都具有非负权的有向图。设s，t是V中的2个顶点，E是e中的一条边，描述一个算法，该算法决定从s到t的所有最短路径是否都包含边e。这就是实现Dijsktra时间复杂度的方法:只需从s运行Dijkstra并计算增量(s，t) (从s到t的最短路径的权重)。删除边e，并从新图中

浏览 6提问于2013-03-04得票数 0

回答已采纳

2回答

dijkstra算法，对某些节点的最短路径只运行一次(不是两个，不是整个图)。

algorithm、graph、graph-algorithm

因此，dijkstra算法是搜索加权(无负)连通图最短路径的最佳算法。Dijkstra算法可用于寻找两点/顶点的最短路径。它可以用来寻找所有顶点的最短路径。问题:我的理解正确吗？它也能用来寻找某些顶点的最短路径吗</em

浏览 2提问于2018-03-12得票数 1

4回答

Dijkstra负权算法

algorithm、dijkstra、shortest-path

首先，我知道Dijkstra不适用于负重，我们可以用Bellman代替它。但是在一个问题中，给出了所有边都有从0到1的权重(0和1不包括在内)。路径的成本实际上是产品。所以我想的是把日志拿走。现在所有的边缘都是负值。现在我知道Dijkstra不会对负重起作用，但是在这种情况下，所有的边都是负的，所以我们不能做一些事情，这样Dijkstra才能工作。我想把所有的权重乘以-1，然后<

浏览 3提问于2015-04-18得票数 7

回答已采纳

1回答

Dijkstra开发了什么算法？

algorithm、computer-science、terminology、dijkstra

我最近问了一个关于Dijkstra算法()的问题。但几乎每个人都认为“Dijkstra算法”是指他的最短路径算法。 Dijkstra还开发了哪些算法？

浏览 0提问于2010-06-02得票数 16

回答已采纳

1回答

当我使用Dijkstra的算法并且一个顶点有多个自循环时，我应该做什么？

graph、graph-theory、shortest-path、dijkstra

我知道平行边，其中有最大的权重，应该删除，并消除自循环，以找到最短的路径。但是，如果一个顶点有多个自循环，并且它们的权重是不同的，那该怎么办？

浏览 2提问于2022-07-18得票数 0

3回答

Dijkstra算法和循环

algorithm、graph-algorithm、dijkstra

一本书中说“Dijkstra的算法只适用于有向无环图”。编辑1："Grokking Algorithms“-Aditya Bhargava一书。

浏览 3提问于2017-04-13得票数 19

1回答

加权无向图上的最长路径

java、algorithm、graph、dijkstra

我知道这是指数级的。我已经实现了一种使用Dijkstra算法寻找最短路径的方法。是否可以修改该方法以找到最长的路径？如果我把所有的重量都减了，这难道不管用吗。我当前图表上的所有权重都是正数。此外，不应该有重复的路径。我知道Bellman Ford算法在负权值下工作，但我希望我能修改我现有的最短</em

浏览 5提问于2013-11-29得票数 1

回答已采纳

5回答

边数固定的最短路径

algorithm、path、dijkstra

在有效时间内通过图找到最短路径，附加的约束是路径必须包含精确的n个节点。我们有一个有向加权图。它可能包含，也可能不包含循环。利用Dijkstra算法可以很容易地找到最短路径，但是Dijkstra算法不能保证边的数目。我们能想到的最好的方法是保存一个节点的最佳n条路径的列表，

浏览 8提问于2009-11-06得票数 3

1回答

没有“前一个”向量的Dijkstra算法

c++、algorithm、dijkstra、breadth-first-search

我感兴趣的是找到图中任何节点和根/源之间的最小距离。所有链接都有权重。我不认为我需要使用中指出的previous[]，因为我不需要知道每个节点的父节点。对吗？另外，如果所有的权重都等于1，我想我可以只运行BFS？

浏览 0提问于2011-01-21得票数 1

回答已采纳

2回答

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

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

所以我来到了这个美丽的问题，它要求你写一个程序，找出在有向图中是否存在负无穷短路径。(也可以认为是查找图中是否存在“负循环”)。下面是这个问题的链接： else

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

回答已采纳

2回答

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

data-structures、graph-theory、dijkstra

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

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

回答已采纳

2回答

具有边代价的Dijkstra最短路径算法

algorithm、shortest-path、dijkstra

我有一个有向的正权重图。每条边都有使用成本。我只有A钱，我想用dijkstra算法计算最短路径，但路径上的边成本总和必须小于或等于A。我想用最小的Dijstra修改来做到这一点(如果我可以用Dijkstra的小修改来做的话)。如果可以的话，我必须用O(n*log(n))来做这件事，但我想我能做到。有人能帮我吗？

浏览 3提问于2010-04-26得票数 9

回答已采纳

1回答

带最小边的Dijkstra算法

algorithm、graph、dijkstra、breadth-first-search

首先，让我们定义算法： Dijkstra算法在具有非负边权的有向图中寻找单源最短路径.如果我有一个源S和目标T，我可以用Dijkstra算法在这两个顶点之间找到最短路径，但是我想要找到这两个顶点之间的最短路径，这两个顶点之间的边数不超过形式K。第一部分是Dijkstra算法，第二部分是BFS算法</em

浏览 2提问于2015-02-16得票数 4

回答已采纳

1回答

两个节点之间的最短路径与从一个节点到所有其他节点的最短路径

algorithm、graph、shortest-path

我目前正在研究非负边权图中的最短路径问题。我知道Dijkstra算法可以给出单源最短路径问题的解决方案，也就是可以找到从一个节点到所有其他节点的最短路径，但是我还没有找到算法，可以给我一个先验的更简单的问题:找到两个节点之间的最短路径。直觉上，我认为可以找到例子，表明“简单”

浏览 4提问于2022-05-11得票数 2

1回答

计算N条最短路径的Dijkstra算法

algorithm、networking、routing、dijkstra、shortest-path

是否可以使用Dijkstra's Algorithm计算从单个源到单个目标的N条最短路径，其中N是节点数？我知道Dijkstra从一个源输出到图中所有节点的最短路径，但当我正在读一篇研究论文时，作者提到了使用Dijkstra计算s和t之间的N条最短路径，这让我有点困惑。以下引用原文：利用基于SDN的SCADA系统:一个反窃听的案例研究-

浏览 0提问于2015-11-25得票数 2

回答已采纳

2回答

为稠密图优化Dijkstra？

path、graph、dijkstra、shortest

除了Dijkstra外，还有另外一种方法来计算近似完全图的最短路径吗？我有大约8,000个节点和大约1,800万个边缘。我已经浏览了线程，并决定使用Dijkstra。我用Perl编写了我的脚本，使用的是Boost：：。但结果和我预期的不一样。使用调用$ 10+ ->Dijkstra最短路径($start_node，$end_node)计算一条最短路径

浏览 4提问于2009-09-12得票数 3

点击加载更多

最佳最短路径算法

寻找最短周期