Bellman-Ford 算法 Space 复杂度

Question

我一直在搜索 Bellman-Ford 算法的 space 复杂性，但在 wikipedia Bellman-Ford Algorithm and it says space complexity is O(V). on this link 上它说 O(V^2) 。我的问题是；真正的 space 复杂度是多少？为什么？

Answer 1

这取决于我们定义它的方式。

如果我们假设图形是给定的，extraspace复杂度是O(V)（对于距离数组） .
如果我们假设图也很重要，那么对于邻接矩阵可以是O(V^2)，对于邻接表可以是O(V+E)。

从某种意义上说，他们都是"true"。这只是关于我们在特定问题中要计算的内容。

Answer 2

有两种情况：-

如果我们假设给定了图形，那么我们必须创建 2 个数组（用于距离数组和父数组）因此，额外的 space 复杂度为 O(五）.
如果我们也考虑图的存储，那么：

a) O(V^2) 邻接矩阵

b) O(V+E) 邻接表

c) O(E) 如果我们只创建将只存储所有边的边列表

Answer 3

不管我们是使用邻接表还是.
邻接矩阵如果给定的图是完整的那么

space complexity = input + extra
1  if we use adjacency matrix,  space = input + extra O(V^2)+O(V) ->Using min heap =O(V^2)
2 if we use adjacency list,  space = input + extraa 
In complite graph E = O(V^2)
O(V + E) + O(V) -> min heap = O(V^2)

因为如果我们谈论 space 的复杂性。
算法我们总是采用最坏的情况。
happen .in Dijkstra 或 bellman ford 都有 complite 图，Space 复杂度 = O(V^2)

Bellman-Ford 算法 Space 复杂度

Bellman-Ford Algorithm Space Complexity

algorithm

space-complexity

graph-algorithm

bellman-ford