腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(1291)
视频
沙龙
2
回答
为什么所有对最
短路
径
算法
都与
负
权值一起工作?
、
、
我最近一直在研究所有对最
短路
径
算法
,比如弗洛伊德-瓦赫尔和约翰逊的
算法
,我注意到这些
算法
产生了正确的解,即使一个图包含
负
权边(但不包含
负
权环)。作为比较,Dijkstra的
算法
(它是单源最
短路
径)不适用于负重边。是什么使全对最
短路
径
算法
在
负
权重的情况下工作?
浏览 9
提问于2014-04-06
得票数 6
回答已采纳
3
回答
给出无向加权连通图,s,t.找到从s到t的路径,使其
最
加权边尽可能低。
、
、
问题:找到一种尽可能高效的
算法
,从s到t返
回路
径。在该路径中,具有最高权重的边缘将具有尽可能少的权重。因此,如果我们从s,t有5条路径,对于每条路径,我们都有最重的边,所以这5的最小边。我试过的是: 使用BFS进行一些修改后,我们根据从s到t的路径数来运行BFS,每次我们找到最大边缘并将其存储在数组中时,我们就会找到数组的最小值。我很难找到一种可以在(1)中运行的
算法
,Bellman ford将
浏览 6
提问于2017-08-02
得票数 3
1
回答
枚举所有最
短路
径
、
、
我需要找到计数并枚举从源节点到目的节点的所有最
短路
径。边可能包含
负
权重。我无法想出一个
算法
来做这件事。 有没有人能帮我弄清楚该怎么做。
浏览 2
提问于2017-11-05
得票数 0
3
回答
最小生成树害怕
负
权重吗?
、
、
、
我认为最
短路
径(SP)有
负
权重的问题,因为它将路径上的所有权重相加,并试图找到最小的一个。我说的对吗?
浏览 7
提问于2012-05-02
得票数 56
回答已采纳
1
回答
Dijkstra
算法
:所有最
短路
径都是非循环的吗?
、
我知道,如果
算法
达到
负
循环,
算法
就不会终止,如果路径包含一个距离大于0的循环,那么它就不是最
短路
径。 我的问题是,如果存在一个循环距离为0的最
短路
径会发生什么,
算法
会将该循环包含在最
短路
径中吗?你会说所有的最
短路
径都是非循环的吗?
浏览 13
提问于2017-06-20
得票数 0
2
回答
检测
负
权重循环的Bellman ford
算法
、
我读过贝尔曼·福特最
短路
径
算法
,它可以检测
负
权重循环。 该
算法
运行(顶点-1)次,以避免无限循环,并成功地检测到
负
权重循环。这很好,但是,我的疑问是,检测
负
权重循环的必要性是什么?当
算法
运行固定次数并自行终止时?
浏览 2
提问于2019-08-19
得票数 0
1
回答
贝尔曼-福特
算法
、
我知道如果图不包含
负
权重循环,Bellman-Ford
算法
最多需要|V| -1次迭代才能找到最
短路
径。有没有办法修改Bellman-Ford
算法
,让它在1次迭代中找到最
短路
径?
浏览 2
提问于2015-02-12
得票数 0
3
回答
最
短路
径:贝尔曼-福特与约翰逊
、
根据维基百科,Johnson
算法
使用Bellman Ford
算法
将边的权重转换为非
负
权重,然后使用Dijkstra
算法
查找最
短路
径。但贝尔曼·福特
算法
也是一种寻找最
短路
径的
算法
。为什么我们不使用从贝尔曼·福特
算法
得到的最
短路
径呢?
浏览 0
提问于2011-03-16
得票数 4
回答已采纳
2
回答
Bellman
算法
能处理正周期吗?
、
我目前正在研究Bellman
算法
,出现了一个疑问。据我所知,Bellman
算法
从它的来源创建最
短路
径,如果图中有一个
负
循环,它返回true,
算法
停止,另一方面,它用最
短路
径返回false。我现在的问题是,该
算法
是避免了图中创建最
短路
径的正循环,还是没有考虑到它们(因而落入了它们的陷阱)? 提前感谢!
浏览 4
提问于2022-01-12
得票数 1
回答已采纳
2
回答
dijkstra
算法
,对某些节点的最
短路
径只运行一次(不是两个,不是整个图)。
、
、
因此,dijkstra
算法
是搜索加权(无
负
)连通图最
短路
径的最佳
算法
。Dijkstra
算法
可用于寻找两点/顶点的最
短路
径。它可以用来寻找所有顶点的最
短路
径。 问题:我的理解正确吗?它也能用来寻找某些顶点的最
短路
径吗?例如,图有A,B,C,D,E,F,G,H,I,J,K,我们只对A,B;C,K的最
短路
感兴趣,我们可能只需要一次就能找到两条路吗?
浏览 2
提问于2018-03-12
得票数 1
2
回答
负
权边有向树的Dijkstra最
短路
径
算法
、
、
、
、
Dijkstra的最
短路
径
算法
会在具有
负
权边的有向树上返回正确的结果吗? 在具有
负
权重的一般图上,该
算法
将失败,但由于它是一棵有向树,因此感觉该
算法
会成功。
浏览 5
提问于2022-06-01
得票数 2
1
回答
可能存在
负
圆时的Floyd-Warshall
算法
、
、
、
所以我的问题是,如果入口图隐藏了
负
圈,会发生什么。输出的dist会代表另一个隐藏了
负
圈的图吗?这不是part 1无效的吗?
浏览 2
提问于2013-06-03
得票数 0
回答已采纳
1
回答
线性时间单对最
短路
径
算法
?
、
、
、
对线性时间中的混合图(即有向和无向边或无向边表示为两条有向边)中的单对最
短路
问题,是否有一种
算法
,具有
负
、实边权和非
负
圈。只提到了问题的单源和全对变体的
算法
.我知道,这些问题中的一个也解决了单对问题,但没有一个在线性时间内工作,而且所有的准则都是这样。 那么,对于具有上述条件的单对最
短路
径问题,是否存在线性时间
算法
呢?
浏览 2
提问于2015-03-16
得票数 0
1
回答
在源点和目标点都可以从
负
循环到达的情况下,是否存在多项式时间最
短路
径
算法
?
、
、
、
我不是要求一个
算法
来检查图中
负
圈的存在(Bellman Ford或Floyd Warshall可以这样做),而是在图包含至少一个从源顶点可以到达的
负
圈,并且从
负
圈可以到达目标顶点的情况下,是否存在多项式时间
算法
来寻找两点之间的最
短路
径
浏览 3
提问于2013-09-02
得票数 2
回答已采纳
1
回答
arangoDB中的多路径搜索
是否有可能在ArangoDB中找到最
短路
径的许多变体?我需要找到许多变体,比如第一个路径距离2,第二个路径距离3等等。是否支持向量权重?
浏览 1
提问于2017-10-28
得票数 1
1
回答
求包含两个节点的最短循环
、
、
设G=(E,V)是具有非
负
边代价的有向图.让我们做一个顶点。我需要找到一个
算法
,为找到每个顶点v,包含s和v的最短循环可能包含几次相同的边。
最
明显的解决办法是从s中运行Dijkstra,以求从s到每个v的最
短路
径,然后从每个v再运行Dijkstra,以求从v到s的最
短路
径,最短的循环是两者的结合。
浏览 2
提问于2013-05-03
得票数 2
回答已采纳
1
回答
带最小边的Dijkstra
算法
、
、
、
首先,让我们定义
算法
:所以我想知道有什么方法可以改变dijkstra来解决
浏览 2
提问于2015-02-16
得票数 4
回答已采纳
4
回答
如何在dijkstra
算法
中保存最
短路
径
、
、
、
首先,让我们定义
算法
:我想知道如何使用Dijkstra
算法
将最
短路
径形式s保存到t。我在谷歌上搜索,但找不到任何特别的东西;我也改变了Dijkstra
算法
,但我无法得到任何答案。如何使用Dijkstra保存从s到t的最
短路
径?
浏览 6
提问于2015-03-11
得票数 11
回答已采纳
1
回答
贝尔曼·福特
算法
在网络中是如何有用的?
、
、
Dijkstra的
算法
比bellman
算法
更有效,但是我们仍然使用bellman
算法
来表示
负
边,但是这些
负
边在网络中代表什么呢?
浏览 4
提问于2013-10-25
得票数 0
回答已采纳
1
回答
区分
负
循环中的节点和可达节点与
负
循环
、
、
我在看WilliamFiset写的关于贝尔曼-福特
算法
的。简而言之,有没有一种方法来区分
负
循环中的节点和
负
循环中可达的节点?而且,仅仅修改贝尔曼-福特
算法
就可以得到吗?
浏览 0
提问于2021-06-17
得票数 0
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
什么是最短路径算法?详述最短路径算法的原理?用C语言实现最短路径算法。内附完整代码。
OSPF 中的最短路径算法:Dijkstra 算法
Python实现平面最短路径算法
图的最短路径算法-Floyd算法-弗洛伊德算法
计量地理学 最短路径算法
热门
标签
更多标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
活动推荐
运营活动
广告
关闭
领券