111111The Shortest Path ProblemShortest-Path AlgorithmsFind the “shortest” path from point A to point B“Shortest” in time, distance, cost, …Numerous applicationsMap navigationFlight itinerariesCircuit wiringNetwork routing22222Shortest Path ProblemsInput is a weighted graph where each edge (vi,vj) has cost ci,jto traverse the edgeCost of a path v1v2…vNis Weighted path costUnweighted path length is N-1, number of edges on path3∑−=+111,NiiicShortest Path ProblemsSingle-source shortest path problemGiven a weighted graph G=(V,E), and a start vertex s, find the minimum weighted path from s to every other vertex in G4Negative WeightsGraphs can have negative weightsE.g., arbitrageShortest positive-weight path is a net gainPath may include individual lossesProblem: Negative weight cyclesAllow arbitrarily-low path costsSolutionDetect presence of negative-weight cycles5Shortest Path ProblemsUnweighted shortest-path problem: O(|E|+|V|)Weighted shortest-path problemNo negative edges: O(|E| log |V|)Negative edges: O(|E|·|V|)Acyclic graphs: O(|E|+|V|)No asymptotically faster algorithm for single-source/single-destination shortest path problem6Unweighted Shortest PathsNo weights on edgesFind shortest length pathsSame as weighted shortest path with all weights equalBreadth-first search7Unweighted Shortest PathsFor each vertex, keep track ofWhether we have visited it (known)Its distance from the start vertex (dv)Its predecessor vertex along the shortest path from the start vertex (pv)8Unweighted Shortest Paths9Solution 1: Repeatedly iterate through vertices, looking for unvisited vertices at current distance from start vertex s.Running time: O(|V|2)Unweighted Shortest Paths10Solution 2: Ignore vertices that have already been visited by keeping only unvisited vertices (distance = ∞) on the queue.Running time: O(|E|+|V|)Unweighted Shortest Paths11Course Evaluation Site in now Open!Check eLearning or course website for URLhttp://skylight.wsu.edu/s/0ef32967-be3f-4f54-b83d-e8d722ea95d3.srvWeighted Shortest PathsDijkstra’s algorithmGREEDY strategy:Always pick the next closest vertex to the sourceUse priority queue to store unvisited vertices by distance from sAfter deleteMin v, update distances of remaining vertices adjacent to v using decreaseKeyDoes not work with negative weights13Dijkstra’s Algorithm1415BuildHeap: O(|V|)DeleteMin: O(|V| log |V|)DecreaseKey: O(|E| log |V|)Total running time: O(|E| log |V|)16DijkstraWhy Dijkstra WorksHypothesisA least-cost path from X to Y contains least-cost paths from X to every city on the path to YE.g., if XC1C2C3Y is the least-cost path from X to Y, thenXC1C2C3 is the least-cost path from X to C3XC1C2 is the least-cost path from X to C2XC1 is the least-cost path from X to C117AD CB201010100100100This is called the “Optimal Substructure” propertyWhy Dijkstra WorksPROOF BY CONTRADICTION:Assume hypothesis is falseI.e., Given a least-cost path P from X to Y that goes through C, there is a better path P’ from X to C than the one in PShow a contradictionBut we could replace the subpath from X to C in P with this lesser-cost path P’The path cost from C to Y is the sameThus we now have a better path from X to YBut this violates the assumption that P is the least-cost path from X to YTherefore, the original hypothesis must be true18X CYP’Printing Shortest Paths19What about graphs with negative edges?Will the O(|E| log|V|) Dijkstra’s algorithm work as is?-10v1v4v2v3321sourceNo change and so v4. dist will remain 4.Correct answer: v4.dist should be updated to -5V3V4.dist = 4, V3.dist = 5 V2No changeV4V2.dist = 3V1Updates to distdeleteMinSolution:Do not mark any vertex as “known”.Instead allow multiple updates.Negative Edge Costs21Running time: O(|E|·|V|)v1v4v2v3321sourceNo updatesV4V4V3V4, V3V2V1QueueV4.dist = -5V3V4.dist = 4, V3.dist = 5 V2No updatesV4V2.dist = 3V1Updates to distDequeue-10Negative Edge Costs22Running time: O(|E|·|V|)Negative weight
View Full Document
Unlocking...