《Discrete Mathematics II教学-华南理工》6.6 Shortest path.pptVIP

Section 9.6 Shortest Path Problem Graphs that have a number assigned to each edge are called weighted graphs. The length of a path in a weighted graph is the sum of the weights of the edges of this path. (note: The use of the the term length is different from the use of length to denote the number of edges in a path in a graph without weight.) Weighted graphs shortest path problem traveling salesman problem 4 2 2 1 5 8 10 3 6 z e d c b a Example The problem of determining the path in a weighted graph such that the sum of the weights of the edges in this path is a minimum over all paths between the specified vertices. SHORTEST PATH PROBLEM Dijkstra’s algorithm. (the shortest path from a to z) The algorithm relies on a series of iterations. A distinguished set of vertices is constructed by adding one vertex at each iteration. A labeling procedure is carried out at each iteration. In labeling procedure, a vertex w is labeled with the length of the shortest path from a to w that contains only vertices already in the distinguished set. The vertex added to the distinguished set is one with minimal label among those vertices not already in the set. A Shortest path algorithm L0(a)=0, L0(v)=?, v: vertices except a. S0=? Sk is formed from Sk-1 by adding a vertex u not in Sk-1 with smallest label. Once u is added to Sk, we update the labels of all vertices not in Sk, so that L k (v), the label of the vertex v at the kth stage, is the length of the shortest path from a to v that contains vertices only in Sk. L k (a,v) = min{L k-1 (a,v), L k-1 (a,u)+w(u,v)} Use Dijkstra’s algorithm to find the length of the shortest path between the vertices a and z in the weighted graph . 4 6 2 1 5 8 10 3 2 z e d c b a 0 ? ? ? ? ? Example 4 6 2 1 5 8 10 3 2 z e d c b a 0 4 ? ? ? 2 4 6 2 1 5 8 10 3 2 z e d c b a 0 3 10 12 ? 2 4 6 2 1 5 8 10 3 2 z e d c b a 0 3 8 12 ? 2 4 6 2 1 5 8 10 3 2 z e d c b a 0 3 8 12 10 2 {a,c} {a,c,b} {a,c,b,d} {a,c,b,d,z} L k (a,v) = min{L k-1 (a