Let G = (V, E) be a weighted graph, where for each edge e = (a, b) in E, wt(a, b) equals the distance from a to b along edge e. If (a, b) ∉ E, then wt(a, b) = ∞.
Fix v0 ∈ V and let S ⊂ V, with v0 ∈ S. Then for S- = V - S we define d(v0, S-) = minves. [d(v0.v) .If vm+1 ∈ S- and d(v0, S) = d(v0, vm+i), then P: (v0, v1), (v1, v2), .. . , (vm-1, vm), (vm, vm+1) is a shortest directed path (in G) from v0 to Vm+1- Prove that
(a) v0, v1 v2, ... , Vm-1, Vm ∈ S.
(b) P': (v0, v1), (v1, v2), . . . , (vk-1, vk) is a shortest directed path (in G) from v0 to vk, for each 1 < k < m.