Log In
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?
in DS 617 views
bellman ford without -ve edge weight , is simply dijkastra

if we update value one by one in directed graph , total updation will be 100
We will get the final result in 2 steps if our order is v1v2,v2v3,v3v4,...v99v100? of we get 100 in this order? would you please submit as an answer?

 v1 --> v2 --> v3 --> v4 --> v5 --> ... v100 

If your graph is like this, then maximum steps will be 100..

For 2 steps, it should be modelled differently..

How to find in just TWO steps?!
for the second case

the solution is 100

if the graph is in straight line form.

What is the meaning of this?

 number of steps is related to checking order of edges

@Arjun sir,

I think that if the graph is like this ==>

v1 --> v2 --> v3 --> v4 --> v5 --> v6 --> ... v100 and all the edge weights are equal to 1.

so, i think graph is topologically sorted by bellman ford and so now we process the edges

 in order (v1,v2) (v2,v3) (v3,v4) (v4,v5) (v5,v6) as the edges in the path in one more than the preceding one.

so, we can find distance from source to any vertex by path relaxation property of bellman ford ....

1 Answer

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

edited by
you copy the answer from those links, I say all of these answer is wrong, please be creative !!

@Sara_Nimlon I didn't literally copy anything . Instead of criticizing ,  could u please tell me what is wrong in it ?

Yes now it's so creative :) thanks, Would you please consider 1) V1-->V2-->V3-->V4....--->V100 ? 2) v99-->v100,v98-->v99,...,v3-->v2,v2-->v1? +1.

Related questions

1 vote
1 answer
What is the reason behind it? How do we find an optimal substructure and overlapping sub problems in this ? In which line of code memoization is done? BELLMAN-FORD(G,w,s) Code 1. INITIALIZE-SINGLE-SOURCE(G,s) 2. for i = 1 to |G.V|-1 3. for each edge (u,v) ∈ G.E 4. RELAX(u,v,w) 5. for each edge (u,v) ∈ G.E ... = NIL 4. s.d = 0 RELAX(u,v,w) 1. if v.d > u.d + w(u,v) 2. v.d = u.d + w(u,v) 3. v.pi = u
asked Aug 3, 2018 in Algorithms Sandy Sharma 540 views
2 votes
1 answer
A pseudo code for Bellman Ford where each edge is relaxed k times where k>=1. Let the graph G be a simple connected and undirected graph . Let number of vertices be V, and number of edges be E . int i=1; for( i=1;i<=k;i++) { For each edge (u,v) in G { if( ... k edges. (ii) For proper running of the algorithm k can be equal to V-1. (iii) For proper running of the algorithm k must be equal to E.
asked Nov 6, 2017 in Algorithms shaurya vardhan 470 views
1 vote
0 answers
Hi Guys, As everyone knows Bellman Ford Algorithm works on DP approach. The algorithm calculate shortest paths in bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, it calculates shortest paths with at-nmost ... converge faster. What is your opinion ? Refer -->
asked Nov 3, 2017 in Algorithms Chhotu 477 views