# Variation on Bellman-Ford Algorithms?

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?

• 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. – D.W. Feb 21 '16 at 18:35
• 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. – D.W. Feb 21 '16 at 18:36

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.