difference constraints using bellman ford

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

difference constraints using bellman ford

Post by tryit1 »

The complexity is O((n+1)*(n+m)) the n in "n+m" and 1 in "n+1" attributed to the 0th vertex .
O(n^2 + nm) , now if i have n=5*10^4 and m=50, how do i reduce to O(nm) ?

Since v0 -> vi is all 0, we can intialize d[vi] = 0;
and then continue bellman ford for the vi vertices ie why do we need the v0 vertex ? We can start from v1 to vk vertices and relax. The final values are the answer for difference constraint . Am i doing anything wrong here ?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: difference constraints using bellman ford

Post by mf »

One way to state the time complexity of Bellman-Ford is O(n + mk), where k is the number of edges in the longest of shortest paths. (Assuming that the algorithm stops as soon as there are no changes in its last iteration.)

And as k <= n-1 and k <= m, that means it runs in O(n + m * min(n, m)) time.

Post Reply

Return to “Algorithms”