算法课件Lecture8章节.pptVIP

Lecture 8Single-Source Shortest Paths Problems Shortest Paths—Notions Related Given a weighted, directed graph G = (V, E; W), the weight of path p = v0, v1, …, vk is the sum of the weights of its constituent edges, that is, Define the shortest-path weight from u to v by A shortest path from vertex u to v is any path p with weight w(p) = ?(u, v). Single-source shortest path problem Input: A weighted directed graph G=(V, E, w), and a source vertex s. Output: Shortest-path weight from s to each vertex v in V, and a shortest path from s to each vertex v in V if v is reachable from s. Notes to Shortest-Paths For single-source shortest-paths problem Negative-weight edge and Negative-weight cycle reachable from s Cycles Can a shortest path contain a cycle? Property of Shortest Paths Lemma 24.1 (Subpaths of shortest paths are shortest paths) Given a weighted, directed graph G = (V, E; W), 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. Why? Can you give a proof? Relaxation Relaxation: Kingsoft 2003, American Traditional Dictionary: A method of solving equations in which the errors resulting from an initial approximation are reduced by succeeding approximations until all errors are within specified limits. In our shortest-paths problem, we maintain an attribute d[v], which is a shortest-path estimate from source s to v. The term RELAXATION is used here for an operation that tightens d[v], or the difference of d[v] and ?(s, v). Relaxation--Initialization The initial estimate of ?(s, v) can be given by: Relaxation Process Relaxing an edge (u, v) consists: Testing whether we can improve the shortest path to v found so far by going through u, and if so, Updating d[v] and ?[v]. A relaxation step may either decrease the value of the shortest-path estimate d[v] and update v’s predecessor ?