Bellman-Ford 的结果是 "all pairs" 还是 "from one node" 最短路径？ / 是否有全对 Bellman-Ford 版本？
Is the result of Bellman-Ford "all pairs" or "from one node" shortest paths? / Is there an all-pairs Bellman-Ford version?
我最近正在学习图形算法，在我的大学里我们被教导，Bellman-Ford 的结果是所有节点到所有其他节点的距离的 table（所有对最短路径） .但是我不明白这个算法是如何实现的，并试图通过观看 YouTube 视频和在维基百科中查找定义等来理解它...
问题来了：
我找不到以结果将是所有对最短路径 table 但只有 "from one node to all other nodes".
的方式描述算法的资源
能否调整 Bellman-Ford 算法以实现所有对的最短路径 table 还是我的大学讲师对此完全错误？ （他确实解释了一些传递所有对最短路径的算法，他称之为 Bellman-Ford，但我认为这不可能是 Bellman Ford）
编辑：我完全理解问题的 Bellman-Ford 算法 "shortest path from one node to all other nodes"。
我也理解我大学 "all pairs shortest paths".
教授的大部分算法
我只是很困惑，因为我大学的算法也被称为 "Bellman-Ford"。
如果你说德语：这是一段视频，大学讲师谈论他的 "Bellman-Ford"（我认为实际上不是 Bellman-Ford）：
https://www.youtube.com/watch?v=3_zqU5GWo4w&t=715s
算法的目的是寻找从起点到终点的最短路径。
为此，它找到从所有点到所有其他点的最短距离，然后 select 找到通向解决方案的路径，并且加起来也是最短的。
首先，它从起点 (A) 开始。将每个点的成本设置为无穷大。
现在它看到了 A 的所有可能方向。并且 A 的初始成本设置为零。
假设它只需要到达 B。可能有一条直线将 B 连接到 A，其成本为 10。
但也有一条路径通过 C。从 A 到 C 需要花费 5，从 C 到 B 只需花费 2。这意味着从 A 到 B 有两条可能的路径。一个有成本 10 和其他 5+2 即 7 。因此它应将到达 B 的成本从 A 更新为 7 而不是 10，因此路径应为 selected。
你可以想象同样的情况，但有更多的分数。它应从起点搜索到终点，遍历所有可能的路径，并 updating/not 在需要时更新成本。最后，它将寻找所有路径，select 成本最小的路径。
Now here comes the problem: a I could not find resources that
described the algorithm in a way that the result would be the all
pairs shortest paths table, but only "from one node to all other
nodes".
要理解这一点，想象一下我们必须达到 A 到 D。
从一个点移动到另一个点的个人成本如下所列
A 到 B :15
A 到 C :10
B 到 C :3
B 到 D :5
C 到 D :15
最初将除 A 之外的所有点设置为无穷大为零。
首先，
A->B : Cost=15（将 B 的成本更新为 15）
A->C : Cost=10（将 C 的成本更新为 10）
B->C : Cost=18(B的成本加上B->C单独的成本，所以不要更新，因为C的成本已经比这个小了)
C->B : Cost=13（C 的成本加上 C->B 单独的成本，将 B 的成本更新为 13，因为它小于 15）
B->D : Cost=18（B 的新成本加上 B->D 单独的成本，更新 D 的成本，因为它小于无穷大）
C->D : Cost=25(C的成本加上C->D单独的成本，不更新D)
所以算法选择的路径是通往D的路径，成本为18，成本最小！
B
/ | \
A | D
\ | /
C
A->C->B->D Cost:18
现在您可以阅读 this link 以获得更好的理解。事情应该很清楚了。
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
我在我们的大学论坛上提问并得到以下答案：
Bellman-Ford 原来是"from one node"。然而，当将原始 Bellman-Ford 算法应用于图的每个节点时，不变量（算法背后的想法）不会改变。
原始 Bellman-Ford 的复杂度是 O(V^3)，如果从每个节点开始，它将是 O(V^4)。然而，有一个可以使用的技巧，因为算法期间的发现类似于输入矩阵（包含直接路径长度）与自身的矩阵乘法。因为这是一个数学环，可以作弊并简单地计算矩阵^2、矩阵^4、矩阵^8等等（这是我没有完全理解的部分）并且可以实现 O(V^3 * log V ).
他也把这个算法叫做Bellman-Ford，因为算法背后的不变性/思想还是一样的。
我最近正在学习图形算法，在我的大学里我们被教导，Bellman-Ford 的结果是所有节点到所有其他节点的距离的 table（所有对最短路径） .但是我不明白这个算法是如何实现的，并试图通过观看 YouTube 视频和在维基百科中查找定义等来理解它...
问题来了：
我找不到以结果将是所有对最短路径 table 但只有 "from one node to all other nodes".
能否调整 Bellman-Ford 算法以实现所有对的最短路径 table 还是我的大学讲师对此完全错误？ （他确实解释了一些传递所有对最短路径的算法，他称之为 Bellman-Ford，但我认为这不可能是 Bellman Ford）
编辑：我完全理解问题的 Bellman-Ford 算法 "shortest path from one node to all other nodes"。
我也理解我大学 "all pairs shortest paths".
教授的大部分算法
我只是很困惑，因为我大学的算法也被称为 "Bellman-Ford"。
如果你说德语：这是一段视频，大学讲师谈论他的 "Bellman-Ford"（我认为实际上不是 Bellman-Ford）：
https://www.youtube.com/watch?v=3_zqU5GWo4w&t=715s
算法的目的是寻找从起点到终点的最短路径。
为此，它找到从所有点到所有其他点的最短距离，然后 select 找到通向解决方案的路径，并且加起来也是最短的。
首先，它从起点 (A) 开始。将每个点的成本设置为无穷大。
现在它看到了 A 的所有可能方向。并且 A 的初始成本设置为零。
假设它只需要到达 B。可能有一条直线将 B 连接到 A，其成本为 10。
但也有一条路径通过 C。从 A 到 C 需要花费 5，从 C 到 B 只需花费 2。这意味着从 A 到 B 有两条可能的路径。一个有成本 10 和其他 5+2 即 7 。因此它应将到达 B 的成本从 A 更新为 7 而不是 10，因此路径应为 selected。
你可以想象同样的情况，但有更多的分数。它应从起点搜索到终点，遍历所有可能的路径，并 updating/not 在需要时更新成本。最后，它将寻找所有路径，select 成本最小的路径。
Now here comes the problem: a I could not find resources that described the algorithm in a way that the result would be the all pairs shortest paths table, but only "from one node to all other nodes".
要理解这一点，想象一下我们必须达到 A 到 D。
从一个点移动到另一个点的个人成本如下所列
A 到 B :15
A 到 C :10
B 到 C :3
B 到 D :5
C 到 D :15
最初将除 A 之外的所有点设置为无穷大为零。
首先，
A->B : Cost=15（将 B 的成本更新为 15）
A->C : Cost=10（将 C 的成本更新为 10）
B->C : Cost=18(B的成本加上B->C单独的成本，所以不要更新，因为C的成本已经比这个小了)
C->B : Cost=13（C 的成本加上 C->B 单独的成本，将 B 的成本更新为 13，因为它小于 15）
B->D : Cost=18（B 的新成本加上 B->D 单独的成本，更新 D 的成本，因为它小于无穷大）
C->D : Cost=25(C的成本加上C->D单独的成本，不更新D)
所以算法选择的路径是通往D的路径，成本为18，成本最小！
B
/ | \
A | D
\ | /
C
A->C->B->D Cost:18
现在您可以阅读 this link 以获得更好的理解。事情应该很清楚了。
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
我在我们的大学论坛上提问并得到以下答案：
Bellman-Ford 原来是"from one node"。然而，当将原始 Bellman-Ford 算法应用于图的每个节点时，不变量（算法背后的想法）不会改变。
原始 Bellman-Ford 的复杂度是 O(V^3)，如果从每个节点开始，它将是 O(V^4)。然而，有一个可以使用的技巧，因为算法期间的发现类似于输入矩阵（包含直接路径长度）与自身的矩阵乘法。因为这是一个数学环，可以作弊并简单地计算矩阵^2、矩阵^4、矩阵^8等等（这是我没有完全理解的部分）并且可以实现 O(V^3 * log V ).
他也把这个算法叫做Bellman-Ford，因为算法背后的不变性/思想还是一样的。