[Solved]: Bellman-Ford Termination when there is no change on vertex weights?

ignougroup
Problem Detail: 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, can we conclude: 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 I Think Neither the number of edges nor their total weight is limited by k-1 with the defining problem, but my TA says (1) is True. How can describe these conditions?

Asked By : Maryam Panahi

Answered By : Yuval Filmus

Part (1) is indeed true. The idea is that in $k$ steps the algorithm is only considering paths of length $k$. Indeed, you can prove by induction on $k$ that the path realizing the value of $d(v)$ after $k$ steps is at most $k$ edges long. If the algorithm terminates after $k$ steps, then the results of the first $k-1$ steps are already optimal, hence (1). Part (2) is indeed false, and I’m sure you can give a counterexample on your own. The simultaneous version of the Bellman–Ford algorithm, referred to in part (1), has the following pseudo-code (where $d(x,y)$ is the weight of the edge connecting $x$ and $y$): 

A[0,x,y] = ∞ for all x,y t ← 0 do   for all x,y:     A[t+1,x,y] = min(A[t,x,y], { A[t,x,z] + d(z,y) : all z ≠ x,y })   t ← t+1 while A[t,x,y] ≠ A[t-1,x,y] for some x,y return A[t,x,y]

Take as an example the (undirected) graph $x – y – z – w$ (with unit weights). Here is a trace of the algorithm: $$ begin{array}{c|cccccc} t & A[t,x,y] & A[t,x,z] & A[t,x,w] & A[t,y,z] & A[t,y,w] & A[t,z,w] hline 0 & infty & infty & infty & infty & infty & infty 1 & 1 & infty & infty & 1 & infty & 1 2 & 1 & 2 & infty & 1 & 2 & 1 3 & 1 & 2 & 3 & 1 & 2 & 1 4 & 1 & 2 & 3 & 1 & 2 & 1 end{array} $$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40848