1,283 views
1 votes
1 votes

In the adjacency list implementation of Bellman Ford algorithm  every edge is visited at most one time  and total of |E| are present in the adjacency list. So,how can the complexity be O(VE) why can't  it be O(E) .Though it has two loops on whole it will  run for |E| times. ??

1 Answer

2 votes
2 votes
what we generally do in bellman ford:-

every time we relax nodes based on the number of nodes that can be used atmost to relax, what i mean first time we relax all node by a distance of one and than relax all nodes by distance two and keep till we reach n-1 times.

We perform relax operation one all outgoing edges of a node. Now consider a complete graph, every time we relax all the edges going out of a node, and such operation done n-1 time => (n-1) * E+ E*1=o(VE)

Related questions

0 votes
0 votes
2 answers
3