Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] نسخه متنی

Optimal substructure of a shortest path

Shortest-paths algorithms typically rely on the property that a shortest path between two vertices contains other shortest paths within it. (The Edmonds-Karp maximum-flow algorithm in Chapter 26 also relies on this property.) This optimal-substructure property is a hallmark of the applicability of both dynamic programming (Chapter 15) and the greedy method (Chapter 16). Dijkstra's algorithm, which we shall see in Section 24.3, is a greedy algorithm, and the Floyd-Warshall algorithm, which finds shortest paths between all pairs of vertices (see Chapter 25), is a dynamic-programming algorithm. The following lemma states the optimal-substructure property of shortest paths more precisely.

Lemma 24.1: (Subpaths of shortest paths are shortest paths)

Given a weighted, directed graph G = (V, E) with weight function w : E → R, let p = 〈v₁, v₂,..., v_k〉 be a shortest path from vertex v₁ to vertex v_k and, for any i and j such that 1 ≤ i ≤ j ≤ k, let p_ij = 〈v_i, v_i+1,..., v_j〉 be the subpath of p from vertex v_i to vertex v_j . Then, p_ij is a shortest path from v_i to v_j.

Proof If we decompose path p into , then we have that w(p) = w(p_1i) + w(p_ij) + w(p_jk). Now, assume that there is a path from v_i to v_j with weight . Then, is a path from v₁ to v_k whose weight is less than w(p), which contradicts the assumption that p is a shortest path from v₁ to v_k.