2
$\begingroup$

We have a Directed Graph with 100 vertexes. v1 --> v2 --> ... v100 and all edges weights is equal to 1. we want to used bellman-ford for finding all shortest paths from v1 to other vertexes. this algorithm in each step check all edges in arbitrary order. if in each step the shortest distance v1 to all others vertexes is not changed, this algorithm halt. the number of steps is related to checking order of edges. what is the minimum and maximum of steps in this problem?

Solution: 2 and 100.

How this solution will be achieved?

$\endgroup$
  • $\begingroup$ What are your thoughts? What have you tried? We want to help you understand concepts, not just do your exercise for you, but as you haven't given us much to work with, it's not clear how to help. $\endgroup$ – D.W. Feb 21 '16 at 18:35
  • $\begingroup$ Cross-posted on SO: stackoverflow.com/q/35526126/781723. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration. $\endgroup$ – D.W. Feb 21 '16 at 18:36
1
$\begingroup$

Since we are checking edges in different order each time, the time taken will depend on the order of the edges being checked in Bellman-Ford algorithm.

We will get the final result in 2 steps if our order is $v_1v_2, v_2v_3, v_3v_4, ... v_{99}v_{100}$.

However we will get the final result in 100 steps if our order is $v_{99}v_{100}, v_{98}v_{99}, ..., v_3v_2, v_2v_1$. We can prove that this is worst possible by noting that in Bellman-Ford algorithm with positive weights, in every iteration at least one shortest distance is calculated correctly. So in first iteration we will only determine the shortest distance to $v_2$, others will remain $\infty$, in second iteration we will determine the shortest distance to $v_2$ and $v_3$ while others still remain $\infty$, and so on so forth.

$\endgroup$
  • $\begingroup$ How we can prove for 2 and 100? $\endgroup$ – user3661613 Feb 20 '16 at 17:10
  • $\begingroup$ I have proved for 100 steps. For 2 steps, you can easily see that Bellman Ford algorithm calculates the correct values in first steps and then terminates in second step, if the choice of edges is done favorably. You need to apply the recursive formula of Bellman Ford algorithm to see how it works. $\endgroup$ – Shreesh Feb 20 '16 at 17:39
  • $\begingroup$ @Shreesh Nice Answer, but I think for solution (2) we should say V1-->V2, V1-->V3,... Isn't it? $\endgroup$ – user4249446 Jun 21 '16 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.