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

Question

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?

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.