【正文】 c e d b 2 4 5 9 6 4 5 5 e a b c d 0 ? ? ? ? Vertex Parent e 91 Prim’ s Algorithm While P is not empty: 1. Select the next vertex u to add to the tree u = () 2. Update the weight of each vertex w adjacent to u which is not in the tree (., w ? P) If weight(u,w) D(w), a. parent(w) = u b. D(w) = weight(u,w) c. Update the priority queue to reflect new distance for w The MST algorithm of Prim ShortestPath Algorithms ? Find the “shortest” path from point A to point B ? “Shortest” in time, distance, cost, … ? Numerous applications ? Map navigation ? Flight itineraries ? Circuit wiring ? Network routing 93 93 The shortest path problems ? Single source shortest path ? Single destination shortest path ? Single pair shortest path ? Allpairs shortest path ? Positive weights on edges ? Negative weights on edges ? Negative cycles ?… Dijkstra’ s Algorithm ? 算法思想 Shortest Paths 95 1 InitializeSingleSource(G,s) 2 S = empty 3 Q = 4 While Q ≠ empty 5 u = ExtractMin(Q) 6 S = S U {u} 7 for each vertex v\in [u] 8 Relax(u,v,w) Running time O(VlgV+E) with using Fibonacci heap Shortest Paths 96 Edge Relaxation ? Consider an edge e ? (u,z) such that ? u is the vertex most recently added to the cloud ? z is not in the cloud ? The relaxation of edge e updates distance d(z) as follows: d(z) ? min{d(z),d(u) ? weight(e)} d(z) ? 75 d(u) ? 50 z s u d(z) ? 60 d(u) ? 50 z s u e e Shortest Paths 97 Example C B A E D F 0 4 2 8 ? ? 4 8 7 1 2 5 2 3 9 C B A E D F 0 3 2 8 5 11 4 8 7 1 2 5 2 3 9 C B A E D F 0 3 2 8 5 8 4 8 7 1 2 5 2 3 9 C B A E D F 0 3 2 7 5 8 4 8 7 1 2 5 2 3 9 Shortest Paths 98 Example (cont.) C B A E D F 0 3 2 7 5 8 4 8 7 1 2 5 2 3 9 C B A E D F 0 3 2 7 5 8 4 8 7 1 2 5 2 3 9 Shortest Paths 99 Why It Doesn’ t Work for NegativeWeight Edges ? If a node with a negative incident edge were to be added late to the cloud, it could mess up distances for vertices already in the cloud. C B A E D F 0 4 5 7 5 9 4 8 7 1 2 5 6 0 8 Dijkstra’s algorithm is based on the greedy method. It adds vertices by increasing distance. C’s true distance is 1, but it is already in the cloud with d(C)=5! The BellmanFord algorithm ? 算法思想 1 InitializeSingleSource(G,w,s) 2 for i =1 to ||1 3 for each edge(u,v)\in 4 relax(u,v,w) 5 for each edge(u,v)\in 6 if +w(u,v) 7 return FALSE 8 return TRUE Running time O(VE) Shortest Paths 101 ? 2 BellmanFord Example ? ? 0 ? ? ? 4 8 7 1 2 5 2 3 9 ? 0 ? ? ? 4 8 7 1 2 5 3 9 Nodes are labeled with their d(v) values 2 2 8 0 4 ? 4 8 7 1 2 5 3 9 ? 8 2 4 1 5 6 1 9 2 5 0 1 1 9 4 8 7 1 2 5 2 3 9 4 a b c d e a b c d e a b c d e a b c d e f f f f SP for Directed Acyclic Graphs (DAG) ? 算法思想 1 Topologically sort the vertices of G 2 InitializeSingleSource(G,s) 3 for each vertex u, taken in topologically sorted order 4 for each vertex v\in [u] 5 Relax(u,v,w) Running time Θ(VE) Example s y x t r 5 6 1 2 3 4 2 z 2 7 1 0 ∞ ∞ ∞ ∞ r t z y ∞ x s ∞ 2 6 6 4 5 3The FloydWarshall algorithm ? 算法思想 )(.1 if ),min(,0 if },...,2,1{set thein are verti cesteinte rmedia all whichfromj toi verte x from pat hsh ortes t a of weigh t the:)( Ej)(i, and ji if Ej)(i, and ji if j)(i, edge direc ted of weigh t thej,i if 0)1()1()1(kijkkkjkikkijijkijkijijijdDkdddkwdkdwWw????????????????????????The FloydWarshall algorithm 1 n= 2 D(0) = W 3 for k = 1 to n 4 let D(k) = (dij(k)) be a new n X n matrix 5 for i = 1 to n 6 for j = 1 to n 7 dij(k) = min(dij(k1), dik(k1) + dkj(k1)) 8 Return D(n) Running time Θ(n3) Example of FloydWarshall 2 4 5 3 1 3 4 2 7 6 4 8 5 1 ??????????????????????????????06052047104830)0(DExample of FloydWarshall ?????????????????????????????0620552047104830)1(D????????????????????????6055211504104830)2(D???????????????????????????06205121150471044830)3(DExample of FloydWarshall ????????????????????????0615820512350471140344130)4(D????????????????????????0615820512350471140342310)4(DThe travelling salesman problem (TSP) ? Heuristics ? Construct a “good” solution from scratch ? Nearest Neighbor () ? Insertion ([log2n]+1) ? Christophide’s algorithm (3/2) ? Improve existing tour by “l(fā)ocal” improvement ? 2Opt (), 3Opt() ? LinKernighan () ? Mimetic algorithms ? Exact Algorithms ? Branchandbound + cutting planes + column generation… Optimal tours 85900 Locations in a VLSI application (2023) Optimal tours 24978 cities in Sweden (2023) 15112 cities in Germany The vehicle routing problem (VRP) ? Capacitated VRP (CVRP) ? CVRP with distance constraints (DCVRP) ? VRP with time windows (VRPTW) ? VRP with backhauls (VRPB) ? VRP with pickup and delivery