self doubt ugcnet

Question

doubt on complexity of bellman ford how it can be O(V2E)

Answer 1

Following are Time Complexity of algorithms

algorithms	Time Complexity	Time Complexity(complete graph)
Bellman Ford	O(VE)	O(V3)
Kruskal	O(E logV)	O(V2 logV)
Prims	O(E logV)	O(V2 logV)
Dijkstra's	O(V + E logV)
Floyd–Warshall's	O(V3)

 

Answer 2

Bellman ford time complexity is O(VE). But in some cases, for example complete graphs, E = O(V²) as any vertex is connected to all other vertices then

Bellman-Fordwill run in O(V^3)

 Relax (V-1) times the number of edges which is in fact 2 nested loop it will take

(v-1)E =O(VE)

And at last will take for each edge belongs to G for detecting all negative cycles it can take O(E) time

So conclusion is O(VE)

Comments

ya that is fine ,,,,so  it cannot be O(v²E) right??