Bellman-Ford and some facts about Graph G?

0
votes

We know the bellman-ford algorithms check all edges in each step, and for each edge if,

d(v)>d(u)+w(u,v)

then d(v) being updated such that w(u,v) is the weight of edge (u, v) and d(u) is the length of best finding path for vertex u. if in one step we have no update for vertexes, the algorithms terminate. with supposing this algorithms, for finding all shortest path from vertex s in graph G with n vertex after k<n iterate is finished, which of the following is correct?

1) number of edges in all shortest paths from s is at most k-1

2) weight of all shortest paths from s is at most k-1

3) Graph has no negative cycle.

I'm sure one of these is True, but My TA says Two of these is correct. any idea or hint for these problem ?

1
mathgraphgraph-theoryshortest-pathbellman-ford
This seems to be a bit too broad for Stack Overflow; perhaps it would be better suited to one of the science SE sites? - GoBusto
what !! too board? no, i dont think so. @GoBusto - user4554402

1 Answers

0
votes

Let's go through the statements one at a time:

1) number of edges in all shortest paths from s is at most k-1

Consider the following graph:

s ---e1---> n1 ---e2---> n2 ---e3---> n3

If the edges are ordered as given (e1, e2, e3), then you will have the correct distance for every node after the first iteration (checking e1 updates n1, then checking e2 updates n2 and so on). So in this case, the algorithm stops after k=2 iterations because the second iteration does not change anything. Number of edges in the longest shortest path is 3 and 3 <= 2-1 does not hold. Hence, this statement is wrong. If, however, all edges are evaluated simultaneously, then the statement is correct (every iteration can go only one edge farther away than the previous iteration).

2) weight of all shortest paths from s is at most k-1

Neither the number of edges nor their total weight is limited by k-1. Consider that all edges in the above example have weight 1000. It is obvious that there is no connection to k.

3) Graph has no negative cycle.

If you define the algorithm as you did (terminates when no changes are made), then this is correct. Any negative cycle would cause an infinite loop because the distances of vertices in this loop successively decrease.