腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
2
回答
为什么所有对
最短
路径
算法
都与负权值一起工作?
algorithm
、
graph
、
shortest-path
我最近一直在研究所有对
最短
路径
算法
,比如
弗洛伊德
-瓦赫尔和约翰逊的
算法
,我注意到这些
算法
产生了正确的解,即使一个图包含负权边(但不包含负权环)。作为比较,Dijkstra的
算法
(它是单源
最短
路径
)不适用于负重边。是什么使全对
最短
路径
算法
在负权重的情况下工作?
浏览 9
提问于2014-04-06
得票数 6
回答已采纳
2
回答
最短
路径
不是图中的
路径
algorithm
、
graph
、
shortest-path
我想知道是否有一种
算法
可以在图中找到
最短
路径
。 假设我有一个图,从一个顶点到另一个顶点有一对
路径
。这些
路径
中的两条或更多条具有相同的成本。如何标记、查找这些顶点之间的所有
最短
路径
?据我所知,Dijkstra或Bellman-Ford
算法
会找到
最短
路径
,但他们只“选择”一条。
浏览 1
提问于2010-08-09
得票数 1
回答已采纳
2
回答
弗洛伊德
·沃肖尔:计算每个顶点对的top-k
最短
路径
algorithm
、
graph
、
shortest-path
、
floyd-warshall
在
弗洛伊德
-沃肖尔
算法
中,为任何一对顶点计算
最短
路径
成本。额外的记账使我们能够将实际
路径
(顶点列表)保持在
最短
路径
上。我如何扩展Floyd-Warshall,以便对任何一对顶点,都能找到top-K
最短
路径
?例如,对于K=3,结果将是计算并维护3条
最短
路径
? 我一直在使用来自Sedgewick的。
浏览 6
提问于2014-08-23
得票数 0
2
回答
具有N个顶点和N个边的图中所有
最短
路径
的优化搜索
algorithm
、
tree
、
graph-theory
、
shortest-path
我需要找到图G中所有对之间的
最短
路径
。我用
弗洛伊德
-沃尔
算法
来计算这个解。 顶点数和边数是相同的。考虑到这些事实,有没有比
弗洛伊德
-沃尔更好的解决办法?
浏览 5
提问于2015-07-14
得票数 1
回答已采纳
1
回答
贝尔曼-福特
算法
和
弗洛伊德
-沃希尔
算法
的基本区别是什么?
algorithm
我只有一个困惑,那就是在贝尔曼-福特
算法
中,我们运行n-1次,这是没有边的,而在Floyd warshall
算法
中,我们在每个阶段运行n次,所以在贝尔曼-福特的情况下,我们排除了源顶点,这就是为什么我们运行
浏览 5
提问于2015-12-25
得票数 9
回答已采纳
2
回答
无向图的最长距离
algorithm
、
graph
、
floyd-warshall
、
undirected-graph
、
longest-path
我想找出一个加权无向图的任意两个顶点之间的最大距离,使用Floyd
算法
。为此,我做了很少的改动: 但它并没有给我正确的输出。
浏览 10
提问于2017-02-28
得票数 1
4
回答
最佳
最短
路径
算法
algorithm
、
shortest-path
“
弗洛伊德
-沃尔”
算法
“和”Dijkstra的
算法
“”之间有什么区别,哪种
算法
是图中
最短
路径
的最佳选择?我需要计算网络中所有对之间的
最短
路径
,并将结果保存到一个数组中,如下所示:A 0 10 15 5 20 B 10
浏览 20
提问于2009-12-04
得票数 27
回答已采纳
1
回答
加权无向图中的所有对
最短
路径
algorithm
、
path-finding
我目前正在为我的游戏寻找
路径
,需要帮助找到一种有效的
算法
来计算加权无向图中的所有对
最短
路径
(图中的每个顶点代表我地图上的一个
路径
点,而每个边表示
路径
对之间的距离)。由于Floyd
算法
的简单性和相对存储效率,我考虑过使用Floyd
算法
,但是Floyd是为有向图设计的,而我的图是无向图。这意味着Floyd
算法
比所需的代价更高,因为我知道从顶点A到顶点B的
最短
路径
总是与从B到A的
最短
<e
浏览 0
提问于2011-09-14
得票数 2
回答已采纳
1
回答
关于
最短
路径
算法
的几个问题
algorithms
、
graph
、
algorithm-analysis
、
dijkstra
我想弄明白为什么有人更喜欢
弗洛伊德
-沃夏尔而不是迪克斯特拉:
弗洛伊德
-沃夏尔做了一个完整的名单和过滤器在那里。
弗洛伊德
-华沙尔,然而,已经开始吐出不同的可能性,并试图一点一滴地改进(例如,基于启发式)。但如果这是真的,那么迪克斯特拉就不会也是这样吗? 还是有其他原因我没有想到这里?
浏览 0
提问于2023-01-20
得票数 1
回答已采纳
2
回答
弗洛伊德
-沃尔
算法
-表示“无穷大”
java
、
graph
、
shortest-path
、
floyd-warshall
使用
弗洛伊德
-沃尔的
算法
寻找两个顶点之间的
最短
路径
,在Java中实现时,我应该如何表示无穷大?我用无穷大来表示两个顶点之间没有
路径
。 谢谢
浏览 4
提问于2014-05-10
得票数 5
回答已采纳
2
回答
有什么
算法
可以找到DAG中的所有关键
路径
吗?
algorithm
、
directed-acyclic-graphs
我正在写一篇关于一些图形
算法
(CPM中使用的)的文章,我需要一些
算法
的名称,它可以找到DAG中的所有关键
路径
。我看过
弗洛伊德
-沃尔
算法
,我不知道它是否能帮助找到DAG中的所有关键
路径
。如果临界
路径
和最长
路径
是相同的,那么Floyd
算法
可以通过在图中寻找所有最长而不是
最短
的
路径
的方式进行修改。即使它可以被修改,是否有更好的方法来找到所有的关键
路径
?
浏览 12
提问于2013-08-26
得票数 1
回答已采纳
1
回答
如何计算节点之间的
最短
可能
路径
?
javascript
、
graph-theory
如果你只能一步一步地从一个节点前进到另一个节点(从A到D,你必须走AB,BC,CD,ED),并且节点之间的距离是可变的,我该如何计算从一个点到另一个点的
最短
可能
路径
?
浏览 18
提问于2018-01-09
得票数 0
回答已采纳
2
回答
比Dijikstra
算法
更快地找到从一个节点开始的所有节点的
最短
路径
algorithm
、
graph
、
path-finding
我正在寻找一种类似于dijikstra的
算法
,但速度更快。我必须解决同样的问题-找到所有节点的
最短
路径
,从给定的节点开始。但是我的老师告诉我,我应该找到一个更快的
算法
,因为dijikstra可能很慢。我还想问问,我能不能用
弗洛伊德
·马歇尔的
算法
来完成这个任务
浏览 6
提问于2022-08-01
得票数 0
回答已采纳
1
回答
在
弗洛伊德
-沃尔内添加负重检查的循环。
algorithm
、
shortest-path
、
floyd-warshall
这是用于
最短
路径
检测的
弗洛伊德
-沃尔
算法
的伪码: 我想知道是否有可能添加一个检查,以测试是否存在负重周期? 我认为这是可能的,但我不知道如何检查。
浏览 3
提问于2022-06-24
得票数 0
回答已采纳
1
回答
具有动态规划的
最短
路径
c
、
dynamic-programming
找到从顶点1到顶点N的
最短
路径
,或者声明这种
路径
不存在。 我把它从另一个问题中拿出来,只是替换了变量名和一些单词,因为它听起来适用于这个问题。我如何表示
最短
的
路径
?它是
路径
的数目,所有
路径</
浏览 2
提问于2016-04-25
得票数 0
回答已采纳
1
回答
GAMS中的Floyd-Warshall
算法
gams-math
我想在GAMS中实现
弗洛伊德
-沃肖尔
算法
。我需要在具有正权重的加权图中找到
最短
路径
。下面是C++中的
算法
P[i][j] = k; }D是原图的邻接矩阵,p是
路径
我能不能把这个
浏览 2
提问于2018-08-31
得票数 1
回答已采纳
2
回答
对于多个敌人和塔的放置,我应该使用哪种
路径
搜索
算法
?
c#
、
unity
、
path-finding
、
tower-defense
我需要一个寻路
算法
来放置我的塔和移动敌人。在寻找
路径
的过程中,我发现了一些
算法
,比如
弗洛伊德
-沃尔,A*,宽度优先,Dijkstra等
算法
。一些答案优先于
弗洛伊德
的
路径
发现与多个敌人。那你建议我用什么来处理我的案子? 我的网格大小是17
浏览 0
提问于2011-10-28
得票数 4
回答已采纳
1
回答
约翰逊
算法
负边距矩阵
algorithm
、
graph
、
shortest-path
得到的矩阵=一个矩阵,其中mati是以顶点I为源,顶点j为目标的
最短
路径
。 我写了我自己的约翰逊
算法
的实现,我想知道它是如何处理负边的?最后,我所获得的距离矩阵与我运行
弗洛伊德
-沃尔时得到的距离矩阵不一样。这一点很明显,因为我们调整了图表的权重。这是否意味着Johnson的
算法
并不能帮助我们找到
最短
路径
的代价,而只是哪条
路径
是
最短
的?另外,如果结果矩阵中的顶点A和顶点B之间有一条
路径
,而在成本为0的顶点A和顶点C之间
浏览 3
提问于2018-12-01
得票数 0
回答已采纳
1
回答
图中k度的LocalBridge
algorithm
、
data-structures
、
graph-theory
在图中找到localbridge(k)的最佳
算法
是什么?k次的局部网桥是一条边,如果去掉它的边,它的两个端点之间的
最短
距离至少会增加到k。 维基百科:
浏览 1
提问于2013-02-28
得票数 6
回答已采纳
2
回答
图中两个节点之间的多重加权边的最小值是最优的吗?
graph
、
dijkstra
、
shortest-path
在加权图中,如果要求计算
最短
路径
.而且,任何两个节点都有可能有多个边,不同的权重将它们连接起来。应用
弗洛伊德
-沃尔
算法
或Dijkstra
算法
:如果两个节点之间存在多个边,我们是否可以取最小加权边而忽略其他边? 如果是的话,有人能证明吗?提前感谢
浏览 3
提问于2013-06-15
得票数 0
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
图的最短路径算法-Floyd算法-弗洛伊德算法
什么是最短路径算法?详述最短路径算法的原理?用C语言实现最短路径算法。内附完整代码。
OSPF 中的最短路径算法:Dijkstra 算法
计量地理学 最短路径算法
揽货最短路径解决方案算法-C#蚁群优化算法实现
热门
标签
更多标签
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
活动推荐
运营活动
广告
关闭
领券