1,196 views
4 votes
4 votes
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 says 2 and 100.

anyone can say how the min and max steps is calculated?

1 Answer

4 votes
4 votes
1) Minimum number of steps for the given problem is 2.
    if the given graph is like
   v1 --> v2
   v1 ---> v3
   :
   :
  v1 --> v100
 in this case, the first iteration will find the distance from source to each edge and second iteration won't change any weight and algorithm will stop.
 
2) Maximum number of steps for the given problem is 100
 
     if  the given graph is like
    v1 --> v2 --> v3 --> v4 ............--> v100
i.e., then all are in stright line. then we need 99 iterations to update the distance to 100 th  vertex and the last iteration won't change the distance.

More References
  1. http://cs.stackexchange.com/questions/53389/variation-on-bellman-ford-algorithms/53391
  2. http://stackoverflow.com/questions/38301744/old-exam-on-bellman-ford-algorithms-need-an-indea
edited by

Related questions

4 votes
4 votes
2 answers
1
Khyati Tuli asked Jul 22, 2016
9,077 views
Is bellman ford a dynamic programming approach? If yes, what is the reason behind it? How do we find an optimal substructure and overlapping sub problems in this ?
0 votes
0 votes
2 answers
3