Bellman-Ford的结果是“所有对”还是“从一个节点”最短的路径？ /是否有全对Bellman-Ford版本？

3 回答

• 4

  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

  回复于 2024-06-02T20:21:22+08:00
• 0

  该算法的目的是找到从起点到终点的最短路径 .

  为此，它找到从所有点到每个其他点的最短距离，然后选择导致解决方案的路径，并且还加起来最短 .

  首先，它从起点（A）开始 . 将每个点的成本设置为无穷大 .

  现在它看到了A的所有可能方向.A的初始成本设置为零 .

  想象一下，它只需要前往B.其中可能有一条将B连接到A的直线路径，其成本就是10 .

  但是也有一条通过C的路径 . 从A到C它需要成本5而从C到B需要成本仅为2.这意味着从A到B有两条可能的路径 . 一条成本为10，另一条成本为10 5 2即7 . 因此，它应将从A到达B的成本更新为不是10，因此应选择路径 .

  你可以想象同样的情况，但还有更多的观点 . 它应从起始点搜索到达遍历所有可能路径的终点，并在需要时更新/不更新成本 . 最后，它应查找所有路径并选择成本最低的路径 .

  现在出现问题：我找不到描述算法的资源，其结果将是所有对最短路径表，但只是“从一个节点到所有其他节点” .

  要理解这一点，想象一下我们必须达到A到D.

  下面列出了从一个点移动到另一个点的单独成本

  • A至B：15

  • A至C：10

  • B到C：3

  • B到D：5

  • C至D：15

  最初将所有点设置为无穷大，除了A到零 .

  第一，

  A-> B：成本= 15（将B的成本更新为15）

  A-> C：成本= 10（将C的成本更新为10）

  B-> C：成本= 18（B的成本加上B-> C单独成本，所以不要更新为C的成本已经小于此值）

  C-> B：成本= 13（C的成本加上C-> B单独成本，将B的成本更新为13，因为它小于15）

  B-> D：成本= 18（B的新成本加B-> D单独成本，更新D的成本，因为这小于无穷大）

  C-> D：成本= 25（C的成本加C-> D单独成本，不更新D）

  因此算法选择的路径是导致D的成本为18，这是最小的成本！

  B  
    /  |  \ 
  A    |   D
    \  | /
       C
  

  A-> C-> B-> D费用：18

  现在您可以阅读this链接以便更好地理解 . 事情应该很清楚 .

  回复于 2024-06-02T20:21:22+08:00
• 1

  一世在我们的大学论坛上询问并得到以下答案：

  Bellman-Ford最初“来自一个节点” . 然而，当将原始Bellman-Ford算法应用于图的每个节点时，不变量（算法引擎下的想法）不会改变 .

  原始Bellman-Ford的复杂性是O（V ^ 3），如果从每个Node开始，它将是O（V ^ 4） . 然而，有一个技巧可以使用，因为算法期间的发现类似于输入矩阵（包含直接路径长度）与其自身的矩阵乘法 . 因为这是一个数学环，人们可以作弊并简单地计算矩阵^ 2，矩阵^ 4，矩阵^ 8等等（这是我不完全理解的部分）并且可以实现O（V ^ 3 * log V ） .

  他把这个算法称为Bellman-Ford，因为算法背后的不变/想法仍然是相同的 .

  German answer in our public university forum

  回复于 2024-06-02T20:21:22+08:00