9.6

来代替null**9.6 Shortest Path Problems null**9.6 Shortest Path Problems null**9.6 Shortest Path Problems null**9.6 Shortest Path Problems null**9.6 Shortest Path Problems null**9.6 Shortest Path Problems null**9.6 Shortest Path Problems null**9.6 Shortest Path Problems null**9.6 Shortest Path Problems 【 Theorem 1】 Dijkstra’s algorithm finds the length of a shortest path between two vertices in a connected simple undirected weighted graph. 迪克斯特拉算法求出连通简单无向 带权图里两个顶点之间最短通路的长度Proof: Take as the induction hypothesis the following assertion: At the kth iteration the label of a vertex v, v0, in S is the length of the shortest path from a to this vertex, and the label of a vertex not in S is the length of the shortest path from a to this vertex that contains only vertices in S. k=0 L0(a)=0, L0(v)= , S=null**9.6 Shortest Path Problems (2) Assume that the inductive hypothesis holds for the kth iteration. Let v be the vertex added to S at the (k+1)st iteration so that v is a vertex not in S at the end of the kth iteration with the smallest label. (I) holds at the end of the (k+1)st iteration The vertices in S before the (k+1)st iteration are labeled with the length of the shortest path from a. v must be labeled with the length of the shortest path to it from a. If this were not the case, at the end of the kth iteration there would be a path of length less than Lk(v) containing a vertex not in S. null**9.6 Shortest Path Problems Let u be the first vertex not in S in such a path. There is a path with length less than Lk(v) from a to u containing only vertices of S. This contradicts the choice of v. (II) is true. Let u be a vertex not in S after k+1 iteration. A shortest path from a to u containing only elements of S either contains v or it does not. If it does not contain v, then by the inductive hypothesis its length is Lk(u). If it does contain v, then it must be made up of a path from a to v of the shortest possible length containing elements of S other than v, followed by the edge from v to u. In this case its length would be Lk(v)+w(v,u). null**9.6 Shortest Path Problems 【 Theorem 2】 Dijkstra’s algorithm uses O(n2 )operations (additions and comparisons) to find the length of the shortest path between two vertices in a connected simple undirected weighted graph. 迪克斯特拉算法使用O( )次运算来求出连 通简单无向带权图里两个顶点之间最短通路的长度Analysis: Use no more than n-1 iteration Each iteration, using no more than n-1 comparisons to determine the vertex not in Sk with the smallest label no more than 2(n-1) operations are used to update no more than n-1 labelsnull**9.6 Shortest Path Problems The Traveling Salesman Problem The traveling salesman problem The traveling salesman problem asks for the circuit of minimum total weight in a weighted, complete, undirected graph that visits each vertex exactly once and returns to its starting point. The equivalent problem: Find a Hamilton circuit with minimum total weight in the complete graph. null**9.6 Shortest Path Problems Solution of the traveling salesman problem (1) A straightforward method Examine all possible Hamilton circuits and select one of minimum total length. The time complexity:(2) Approximation algorithm For example,The length of this path: 40 The exact solution ( the length is 37 ):a,c,e,b,d,anull**9.6 Shortest Path Problems Solution of the traveling salesman problem (1) A straightforward method Examine all possible Hamilton circuits and select one of minimum total length. The time complexity:(2) Approximation algorithm The time complexity:null**9.6 Shortest Path Problems Homework: P. 601 2, 26