Optimal substructure of a shortest path

| < Day Day Up > |

#### 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 = 〈v1, v2,..., vk〉 be a shortest path from vertex v1 to vertex vk and, for any i and j such that 1 ≤ i ≤ j ≤ k, let pij = 〈vi, vi+1,..., vj〉 be the subpath of p from vertex vi to vertex vj . Then, pij is a shortest path from vi to vj.

Proof If we decompose path p into , then we have that w(p) = w(p1i) + w(pij) + w(pjk). Now, assume that there is a path from vi to vj with weight . Then, is a path from v1 to vk whose weight is less than w(p), which contradicts the assumption that p is a shortest path from v1 to vk.

| < Day Day Up > |