Let G = (V, E) be a weighted, directed graph that contains no negative-weight cycles. Let s

Question:

Let G = (V, E) be a weighted, directed graph that contains no negative-weight cycles. Let s ¬ V be the source vertex, and let G be initialized by INITIALIZE-SINGLE-SOURCE (G, s). Prove that there exists a sequence of |V | - 1 relaxation steps that produces d[v] = δ(s, v) for all v ⁪ ¬ V.