Graph AlgorithmsShortest-Path AlgorithmsShortest Path ProblemsShortest Path ProblemsNegative WeightsShortest Path ProblemsUnweighted Shortest PathsUnweighted Shortest PathsUnweighted Shortest PathsUnweighted Shortest PathsUnweighted Shortest PathsWeighted Shortest PathsDijkstra’s AlgorithmSlide Number 14Slide Number 15Why Dijkstra WorksWhy Dijkstra WorksPrinting Shortest PathsNegative Edge Costs111111Graph AlgorithmsCptS 223 – Advanced Data StructuresLarry HolderSchool of Electrical Engineering and Computer ScienceWashington State UniversityShortest-Path 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 routing22222Shortest Path Problems Input is a weighted graph where each edge (vi,vj) has cost ci,jto traverse the edge Cost of a path v1v2…vNis Weighted path cost Unweighted path length is N-1, number of edges on path3∑−=+111,NiiicShortest Path Problems Single-source shortest path problem Given a weighted graph G=(V,E), and a start vertex s, find the minimum weighted path from s to every other vertex in G4Negative Weights Graphs can have negative weights E.g., arbitrage Shortest positive-weight path is a net gain Path may include individual losses Problem: Negative weight cycles Allow arbitrarily-low path costs Solution Detect presence of negative-weight cycles5Shortest Path Problems Unweighted shortest-path problem: O(|E|+|V|) Weighted shortest-path problem No 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 Paths No weights on edges Find shortest length paths Same as weighted shortest path with all weights equal Breadth-first search7Unweighted Shortest Paths For each vertex, keep track of Whether 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 Paths11Weighted Shortest Paths Dijkstra’s algorithm Use priority queue to store unvisited vertices by distance from s After deleteMin v, update distances of remaining vertices adjacent to v using decreaseKey Does not work with negative weights12Dijkstra’s Algorithm1314BuildHeap: O(|V|)DeleteMin: O(|V| log |V|)DecreaseKey: O(|E| log |V|)Total running time: O(|E| log |V|)15DijkstraWhy Dijkstra Works Hypothesis A least-cost path from X to Y contains least-cost paths from X to every city on the path E.g., if XÆC1ÆC2ÆC3ÆY is the least-cost path from X to Y, then XÆC1ÆC2ÆC3 is the least-cost path from X to C3 XÆC1ÆC2 is the least-cost path from X to C2 XÆC1 is the least-cost path from X to C116AD CB201010100100100Why Dijkstra Works Assume hypothesis is false I.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 P Show a contradiction But 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 same Thus we now have a better path from X to Y But this violates the assumption that P is the least-cost path from X to Y Therefore, the original hypothesis must be true17XCYP’Printing Shortest Paths18Negative Edge Costs19Running time: O(|E|·|V|)Negative weight
View Full Document
Unlocking...