The Shortest Path ProblemThe Shortest Path Problem

1 The Shortest path ProblemThe Shortest path Problem111111 Cpt S 223. School of EECS, WSUS hortest- path Algorithms Find the Shortest path from point A to point B Shortest in time, distance, cost, .. Numerous applications Numerous applications Map navigation Flight itineraries Circuit wiring Network routing22222 Cpt S 223. School of EECS, WSUS hortest path ProblemsWeighted graphs: Input is a weighted graph where each edge (vi,vj) pggpg(i,j)has cost ci,jto traverse the edge Cost of a path 111,Niiic Goal:to find a smallest cost pathUnweighted graphs: Input is an unweighted graph , all edges are of equal weightGoal:to find a path with smallest number of hops3 Cpt S 223. School of EECS, WSUS hortest path ProblemsSingle-source Shortest path Problem Given a weighted graph G=(V,E), and a Given a weighted graph G(V,E), and a source vertex s, find the minimum weighted path from s to every other vertexin GWeighted:Some algorithms:s: sourceDijkstra s algoUnweighted:Simple BFS4 Simple BFSCpt S 223.

2 School of EECS, WSUP oint to Point SP problemGiven G(V,E) and two vertices A and B, find a Shortest path from A (source)to p()B (destination).Solution:1) Run the code for Single Source1) Run the code for Single Source Shortest path using source as ) Stop algorithm when B is ) Stop algorithm when B is S 223. School of EECS, WSUAll Pairs Shortest path ProblemGiven G(V,E), find a Shortest path between all pairs of :(brute-force)(bruteforce)Solve Single Source Shortest path for each vertex as sourceThere are more efficient ways of solving this Problem ( , Floyd-Warshall algo). Problem ( , FloydWarshall algo).6 Cpt S 223. School of EECS, WSUN egative Weights Graphs can have negative weights , arbitrage Shortest positive-weight path is a net gain path may include individual losses Problem : Negative weight cyclesAllow arbitrarilylow path costs Allow arbitrarily-low path costs Solution Detect presence of negative-weight pggcycles7 Cpt S 223.

3 School of EECS, WSUU nweighted Shortest Paths No weights on edges Find Shortest length paths Find Shortest length paths Same as weighted Shortest path with all weights equalweights equal Breadth-first search12source023O(|E| + |V|)813O(|E| + |V|)Cpt S 223. School of EECS, WSUU nweighted Shortest Paths For each vertex, keep track of Whether we have visited it (known) Whether we have visited it (known) Its distance from the start vertex (dv) Its predecessor vertex along the Shortest Its predecessor vertex along the Shortest path from the start vertex (pv)9 Cpt S 223. School of EECS, WSUU nweighted Shortest PathsSolution 1: Repeatedly iterate through vertices, looking for unvisited vertices at current distance from start vertex time: O(|V|2)10 Cpt S 223. School of EECS, WSUU nweighted Shortest PathsSolution:Ignore vertices that have already been visited by keeping only yypgyunvisited vertices (distance = ) on the (|E|+|V|)Running time:O(|E|+|V|)source11 Queue:v3v1, v6v2, v4v7, v5 Cpt S 223.

4 School of EECS, WSUU nweighted Shortest Paths12 Cpt S 223. School of EECS, WSUW eighted Shortest Paths Dijkstra s algorithm GREEDY strategy: Always pick the next closest vertex to the source Use priority queue to store unvisited vertices by distance from sdistance from s After deleteMin v, update distances of remaining vertices adjacent to v using decreaseKey Does not work with negative weights13 Cpt S 223. School of EECS, WSUD ijkstra s Algorithm14 Cpt S 223. School of EECS, WSUsourceDijkstra15 Cpt S 223. School of EECS, WSUB uildHeap: O(|V|)DeleteMin: O(|V| log |V|)DecreaseKey: O(|E| log |V|)16 Total running time: O(|E| log |V|)Cpt S 223. School of EECS, WSUWhy Dijkstra Works Hypothesis Aleast-cost path from X to Y containsThis is called the Optimal Substructure property A leastcost path from X to Y contains least-cost paths from X to every city on the path to Y , 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 C1AB2010100100 X C1 is the leastcost path from X to C117DC10100 Cpt S 223.

5 School of EECS, WSUWhy Dijkstra WorksXCY PROOF BY CONTRADICTION: Assume hypothesis is falseYP , 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 contradictionSo acotadcto 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 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 Yfrom X to Y Therefore, the original hypothesis must be true18 Cpt S 223. School of EECS, WSUP rinting Shortest Paths19 Cpt S 223. School of EECS, WSUWhat about graphs with negative edges? Will the O(|E| log|V|) Dijkstra s algorithm work as is?algorithm work as is?deleteMinUpdates to distVVdi = = 4, = 5 V4No changeVNo change and so vdist will-10v4v3V3No change and so v4. dist will remain should be updated to -5 Solution:Do not mark any vertex as known.

6 Instead allow multiple S 223. School of EECS, WSUN egative Edge CostsRunning time: O(|E| |V|) = 3V1 Updates to distDequeueV3V4, = = 4, = 5 V2No updatesV421No updatesV4V4 Cpt S 223. School of EECS, WSUN egative Edge CostsRunning time: O(|E| |V|)Negative weight cycles?ggy2222 Cpt S 223. School of EECS, WSUS hortest 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|) Acyclic graphs: O(|E|+|V|) No asymptotically faster algorithm for single-source/single-destination Shortest path problem2323 Cpt S 223. School of EECS, WSUCEltiSitiCourse Evaluation Site in now Open!Open!http://skylight wsu edu/s/053eadf6-6157-44ce- S 223. School of EECS, WSU