gpt4 book ai didi

algorithm - Bellman-Ford 的结果是 "all pairs"还是 "from one node"最短路径?/是否有全对 Bellman-Ford 版本?

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:33:39 26 4
gpt4 key购买 nike

我最近在学习图形算法,在我的大学里我们被教导,Bellman-Ford 的结果是一个所有节点到所有其他节点的距离表(所有对最短路径)。但是我不明白这个算法是如何实现的,并试图通过观看 YouTube 视频和在维基百科中查找定义等来理解它......

问题来了:
我找不到以结果是所有对最短路径表的方式描述算法的资源,但只是“从一个节点到所有其他节点”。

是否可以调整 Bellman-Ford 算法以获得所有对最短路径表,或者我的大学讲师对此完全错误? (他确实解释了一些传递所有对最短路径的算法,他称之为 Bellman-Ford,但我认为这不可能是 Bellman Ford)

编辑:我完全理解“从一个节点到所有其他节点的最短路径”问题的 Bellman-Ford 算法。
我也理解我大学教授的“所有对最短路径”的大部分算法。
我只是很困惑,因为我大学的算法也被称为“Bellman-Ford”。
如果你说德语:这是一段视频,大学讲师谈论他的“Bellman-Ford”(我认为实际上不是 Bellman-Ford):
https://www.youtube.com/watch?v=3_zqU5GWo4w&t=715s

最佳答案

Bellman Ford 是用于查找从给定起始节点到图中任何其他节点的最短路径的算法。

如果我们从每个节点运行 bellman ford 算法然后获得到所有其他节点的最短路径,则使用 Bellman Ford 我们可以生成所有对的最短路径,但该算法的最坏情况时间复杂度将为 O(V * V * E) 如果我们有完整的图,这个复杂度将是 O (V^4),其中 V 是图中顶点(节点)的数量, E 是图中的边数。

有更好的算法可以在 O(V^3) 时间复杂度内找到所有对的最短路径。这就是 Floyd Warshall 算法。

在这里您可以阅读更多相关信息:https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

关于algorithm - Bellman-Ford 的结果是 "all pairs"还是 "from one node"最短路径?/是否有全对 Bellman-Ford 版本?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45127379/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com