Bellman-Ford Algorithm Space Complexity

Question

I have been searching about Bellman-Ford Algorithm's space complexity but on wikipedia Bellman-Ford Algorithm and it says space complexity is O(V). on this link it says O(V^2) . My question is; what is the true space complexity and why?

Answer 1

It depends on the way we define it.

1. If we assume that the graph is given, the extra space complexity is O(V) (for an array of distances).

2. If we assume that the graph also counts, it can be O(V^2) for an adjacency matrix and O(V+E) for an adjacency list.

They both are "true" in some sense. It's just about what we want to count in a specific problem.

Answer 2

It does not matter whether we are using adjacency list or.
adjacency matrix if given graph is complete one then

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)

Because if we talk about space complexity for an.
algorithm we always go with worst case what can be.
happen .in Dijkstra or bellman ford both have complite Graph, Space Complexity is = O(V^2)

Answer 3

There are two cases:-

1. If we assume that the graph is given, then we have to create 2 arrays (for an array of distances and array of parents) so, the extra space complexity is O(V) .

2. If we consider storing of graph also then:

   a) O(V^2) for adjacency matrix

   b) O(V+E) for adjacency list

   c) O(E) if we just create edges list which will store all the edges only