Question? Leave a message!




shortest-paths properties and Algorithms

shortest-paths properties and Algorithms
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 4.4 SHORTEST PATHS APIs ‣ shortestpaths properties ‣ Dijkstra's algorithm ‣ Algorithms FOUR TH EDITION edgeweighted DAGs ‣ negative weights ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduShortest paths in an edgeweighted digraph Given an edgeweighted digraph, find the shortest path from s to t. edgeweighted digraph 45 0.35 54 0.35 47 0.37 57 0.28 75 0.28 51 0.32 04 0.38 02 0.26 73 0.39 shortest path from 0 to 6 13 0.29 02 0.26 27 0.34 27 0.34 62 0.40 73 0.39 36 0.52 36 0.52 60 0.58 64 0.93 An edgeweighted digraph and a shortest path 2Google maps 3Shortest path applications PERT/CPM. Map routing. Seam carving. Texture mapping. Robot navigation. http://en.wikipedia.org/wiki/Seamcarving Typesetting in TeX. Urban traffic planning. Optimal pipelining of VLSI chip. Telemarketer operator scheduling. Routing of telecommunications messages. Network routing protocols (OSPF, BGP, RIP). Exploiting arbitrage opportunities in currency exchange. Optimal truck routing through given traffic congestion pattern. Reference: Network Flows: Theory, Algorithms, and Applications, R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Prentice Hall, 1993. 4Shortest path variants Which vertices Single source: from one vertex s to every other vertex. Single sink: from every vertex to one vertex t. Sourcesink: from one vertex s to another t. All pairs: between all pairs of vertices. Restrictions on edge weights Nonnegative weights. Euclidean weights. Arbitrary weights. Cycles No directed cycles. which variant No "negative cycles." Simplifying assumption. Shortest paths from s to each vertex v exist. 54.4 SHORTEST PATHS APIs ‣ shortestpaths properties ‣ Dijkstra's algorithm ‣ Algorithms edgeweighted DAGs ‣ negative weights ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduWeighted directed edge API public class public class public class DirectedEdge DirectedEdge DirectedEdge DirectedEdge(int v, int w, double weight) weighted edge v→w int from() vertex v int to() vertex w double weight() weight of this edge String toString() string representation weight v w Idiom for processing an edge e: int v = e.from(), w = e.to(); 7Weighted directed edge: implementation in Java Similar to Edge for undirected graphs, but a bit simpler. public class DirectedEdge private final int v, w; private final double weight; public DirectedEdge(int v, int w, double weight) this.v = v; this.w = w; this.weight = weight; public int from() from() and to() replace return v; either() and other() public int to() return w; public int weight() return weight; 8Edgeweighted digraph API public class public class EdgeWeightedDigraph EdgeWeightedDigraph EdgeWeightedDigraph(int V) EdgeWeightedDigraph(int V) edgeweighted digraph with V vertices EdgeWeightedDigraph(In in) EdgeWeightedDigraph(In in) edgeweighted digraph from input stream void addEdge(DirectedEdge e) addEdge(DirectedEdge e) add weighted directed edge e IterableDirectedEdge adj(int v) adj(int v) edges pointing from v int V() V() number of vertices int E() E() number of edges IterableDirectedEdge edges() edges() all edges String toString() toString() string representation Conventions. Allow selfloops and parallel edges. 9Edgeweighted digraph: adjacencylists representation tinyEWD.txt 0 2 .26 0 4 .38 V 8 E 15 1 3 .29 4 5 0.35 adj 5 4 0.35 0 4 7 0.37 2 7 .34 Bag objects 1 5 7 0.28 7 5 0.28 2 3 6 .52 reference to a 5 1 0.32 3 DirectedEdge 0 4 0.38 object 4 0 2 0.26 4 7 .37 4 5 .35 7 3 0.39 5 1 3 0.29 6 5 1 .32 5 7 .28 5 4 .35 2 7 0.34 7 6 2 0.40 3 6 0.52 6 4 .93 6 0 .58 6 2 .40 6 0 0.58 6 4 0.93 7 3 .39 7 5 .28 Edgeweighted digraph representation 10Edgeweighted digraph: adjacencylists implementation in Java Same as EdgeWeightedGraph except replace Graph with Digraph. public class EdgeWeightedDigraph private final int V; private final BagDirectedEdge adj; public EdgeWeightedDigraph(int V) this.V = V; adj = (BagDirectedEdge) new BagV; for (int v = 0; v V; v++) adjv = new BagDirectedEdge(); public void addEdge(DirectedEdge e) add edge e = v→w to int v = e.from(); adjv.add(e); only v's adjacency list public IterableDirectedEdge adj(int v) return adjv; 11Singlesource shortest paths API Goal. Find the shortest path from s to every other vertex. public class public class public class SP SP SP SP(EdgeWeightedDigraph G, int s) shortest paths from s in graph G double distTo(int v) length of shortest path from s to v Iterable DirectedEdge pathTo(int v) shortest path from s to v boolean hasPathTo(int v) is there a path from s to v SP sp = new SP(G, s); for (int v = 0; v G.V(); v++) StdOut.printf("d to d (.2f): ", s, v, sp.distTo(v)); for (DirectedEdge e : sp.pathTo(v)) StdOut.print(e + " "); StdOut.println(); 12Singlesource shortest paths API Goal. Find the shortest path from s to every other vertex. public class public class public class SP SP SP SP(EdgeWeightedDigraph G, int s) shortest paths from s in graph G double distTo(int v) length of shortest path from s to v Iterable DirectedEdge pathTo(int v) shortest path from s to v boolean hasPathTo(int v) is there a path from s to v java SP tinyEWD.txt 0 0 to 0 (0.00): 0 to 1 (1.05): 04 0.38 45 0.35 51 0.32 0 to 2 (0.26): 02 0.26 0 to 3 (0.99): 02 0.26 27 0.34 73 0.39 0 to 4 (0.38): 04 0.38 0 to 5 (0.73): 04 0.38 45 0.35 0 to 6 (1.51): 02 0.26 27 0.34 73 0.39 36 0.52 0 to 7 (0.60): 02 0.26 27 0.34 134.4 SHORTEST PATHS APIs ‣ shortestpaths properties ‣ Dijkstra's algorithm ‣ Algorithms edgeweighted DAGs ‣ negative weights ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduData structures for singlesource shortest paths Goal. Find the shortest path from s to every other vertex. Observation. A shortestpaths tree (SPT) solution exists. Why Consequence. Can represent the SPT with two vertexindexed arrays: distTov is length of shortest path from s to v. edgeTov is last edge on shortest path from s to v. edgeTo distTo edgeTo distTo 0 null 0 0 null 0 1 51 0.32 1.05 1 51 0.32 1.05 2 02 0.26 0.26 2 02 0.26 0.26 3 73 3 73 0.37 0.37 0.97 0.97 4 04 0.38 0.38 4 04 0.38 0.38 5 45 0.35 0.73 5 45 0.35 0.73 6 36 0.52 1.49 6 36 0.52 1.49 7 27 0.34 0.60 7 27 0.34 0.60 Shortest paths data structures shortestpaths tree from 0 parentlink representation Shortest paths data structures 15Data structures for singlesource shortest paths Goal. Find the shortest path from s to every other vertex. Observation. A shortestpaths tree (SPT) solution exists. Why Consequence. Can represent the SPT with two vertexindexed arrays: distTov is length of shortest path from s to v. edgeTov is last edge on shortest path from s to v. public double distTo(int v) return distTov; public IterableDirectedEdge pathTo(int v) StackDirectedEdge path = new StackDirectedEdge(); for (DirectedEdge e = edgeTov; e = null; e = edgeToe.from()) path.push(e); return path; 16Edge relaxation Relax edge e = v→w. distTov is length of shortest known path from s to v. distTow is length of shortest known path from s to w. edgeTow is last edge on shortest known path from s to w. If e = v→w gives shorter path to w through v, update both distTow and edgeTow. v→w successfully relaxes v 3.1 1.3 s w 7.2 4.4 black edges are in edgeTo 17Edge relaxation Relax edge e = v→w. distTov is length of shortest known path from s to v. distTow is length of shortest known path from s to w. edgeTow is last edge on shortest known path from s to w. If e = v→w gives shorter path to w through v, update both distTow and edgeTow. private void relax(DirectedEdge e) int v = e.from(), w = e.to(); if (distTow distTov + e.weight()) distTow = distTov + e.weight(); edgeTow = e; 18Shortestpaths optimality conditions Proposition. Let G be an edgeweighted digraph. Then distTo are the shortest path distances from s iff: distTos = 0. For each vertex v, distTov is the length of some path from s to v. For each edge e = v→w, distTow ≤ distTov + e.weight(). Pf. ⇐ necessary Suppose that distTow distTov + e.weight() for some edge e = v→w. Then, e gives a path from s to w (through v) of length less than distTow. distTov v 3.1 1.3 s distTow w 7.2 19Shortestpaths optimality conditions Proposition. Let G be an edgeweighted digraph. Then distTo are the shortest path distances from s iff: distTos = 0. For each vertex v, distTov is the length of some path from s to v. For each edge e = v→w, distTow ≤ distTov + e.weight(). Pf. ⇒ sufficient Suppose that s = v → v → v → … → v = w is a shortest path from s to w. 0 1 2 k Then, distTov distTov + e .weight() 1 0 1 ≤ th e = i edge on shortest i distTov distTov + e .weight() 2 1 2 ≤ path from s to w ... distTov distTov + e .weight() k k1 k ≤ Add inequalities; simplify; and substitute distTov = distTos = 0: 0 distTow = distTov ≤ e .weight() + e .weight() + … + e .weight() k 1 2 k weight of shortest path from s to w Thus, distTow is the weight of shortest path to w. weight of some path from s to w 20Generic shortestpaths algorithm Generic algorithm (to compute SPT from s) Initialize distTos = 0 and distTov = ∞ for all other vertices. Repeat until optimality conditions are satisfied: Relax any edge. Proposition. Generic algorithm computes SPT (if it exists) from s. Pf sketch. The entry distTov is always the length of a simple path from s to v. Each successful relaxation decreases distTov for some v. The entry distTov can decrease at most a finite number of times. 21Generic shortestpaths algorithm Generic algorithm (to compute SPT from s) Initialize distTos = 0 and distTov = ∞ for all other vertices. Repeat until optimality conditions are satisfied: Relax any edge. Efficient implementations. How to choose which edge to relax Ex 1. Dijkstra's algorithm (nonnegative weights). Ex 2. Topological sort algorithm (no directed cycles). Ex 3. BellmanFord algorithm (no negative cycles). 224.4 SHORTEST PATHS APIs ‣ shortestpaths properties ‣ Dijkstra's algorithm ‣ Algorithms edgeweighted DAGs ‣ negative weights ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduEdsger W. Dijkstra: select quotes “ Do only what only you can do. ” “ In their capacity as a tool, computers will be but a ripple on the surface of our culture. In their capacity as intellectual challenge, they are without precedent in the cultural history of mankind. ” “ The use of COBOL cripples the mind; its teaching should, Edsger W. Dijkstra therefore, be regarded as a criminal offence. ” Turing award 1972 “ It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration. ” “ APL is a mistake, carried through to perfection. It is the language of the future for the programming techniques of the past: it creates a new generation of coding bums. ” 24Edsger W. Dijkstra: select quotes 25Dijkstra's algorithm demo Consider vertices in increasing order of distance from s (nontree vertex with the lowest distTo value). Add vertex to tree and relax all edges pointing from that vertex. 0→1 5.0 1 3 15 0→4 9.0 5 0→7 8.0 4 12 3 s 0 1→2 12.0 8 1→3 15.0 9 7 2 7 1→7 4.0 2→3 3.0 9 6 1 11 2→6 11.0 5 3→6 9.0 5 4→5 4.0 4 13 4→6 20.0 6 4 20 4→7 5.0 5→2 1.0 5→6 13.0 an edgeweighted digraph 7→5 6.0 7→2 7.0 26Dijkstra's algorithm demo Consider vertices in increasing order of distance from s (nontree vertex with the lowest distTo value). Add vertex to tree and relax all edges pointing from that vertex. 1 3 v distTo edgeTo 0 0.0 1 5.0 0→1 s 0 2 14.0 5→2 7 2 3 17.0 2→3 4 9.0 0→4 5 13.0 4→5 5 6 25.0 2→6 7 8.0 0→7 6 4 shortestpaths tree from vertex s 27Dijkstra's algorithm visualization 28Dijkstra's algorithm visualization 29Dijkstra's algorithm: correctness proof Proposition. Dijkstra's algorithm computes a SPT in any edgeweighted digraph with nonnegative weights. Pf. Each edge e = v→w is relaxed exactly once (when vertex v is relaxed), leaving distTow ≤ distTov + e.weight(). Inequality holds until algorithm terminates because: distTo values are monotone decreasing – distTow cannot increase we choose lowest distTo value at each step – distTov will not change (and edge weights are nonnegative) Thus, upon termination, shortestpaths optimality conditions hold. 30Dijkstra's algorithm: Java implementation public class DijkstraSP private DirectedEdge edgeTo; private double distTo; private IndexMinPQDouble pq; public DijkstraSP(EdgeWeightedDigraph G, int s) edgeTo = new DirectedEdgeG.V(); distTo = new doubleG.V(); pq = new IndexMinPQDouble(G.V()); for (int v = 0; v G.V(); v++) distTov = Double.POSITIVEINFINITY; distTos = 0.0; pq.insert(s, 0.0); relax vertices in order while (pq.isEmpty()) of distance from s int v = pq.delMin(); for (DirectedEdge e : G.adj(v)) relax(e); 31Dijkstra's algorithm: Java implementation private void relax(DirectedEdge e) int v = e.from(), w = e.to(); if (distTow distTov + e.weight()) distTow = distTov + e.weight(); edgeTow = e; if (pq.contains(w)) pq.decreaseKey(w, distTow); update PQ else pq.insert (w, distTow); 32Dijkstra's algorithm: which priority queue Depends on PQ implementation: V insert, V deletemin, E decreasekey. PQ implementation insert deletemin decreasekey total 2 unordered array 1 V 1 V binary heap log V log V log V E log V dway heap log V d log V log V E log V d d d E/V † † † Fibonacci heap 1 log V 1 E + V log V † amortized Bottom line. Array implementation optimal for dense graphs. Binary heap much faster for sparse graphs. 4way heap worth the trouble in performancecritical situations. Fibonacci heap best in theory, but not worth implementing. 33Computing a spanning tree in a graph Dijkstra's algorithm seem familiar Prim's algorithm is essentially the same algorithm. Both are in a family of algorithms that compute a spanning tree. Main distinction: Rule used to choose next vertex for the tree. Prim: Closest vertex to the tree (via an undirected edge). Dijkstra: Closest vertex to the source (via a directed path). Note: DFS and BFS are also in this family of algorithms. 344.4 SHORTEST PATHS APIs ‣ shortestpaths properties ‣ Dijkstra's algorithm ‣ Algorithms edgeweighted DAGs ‣ negative weights ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduAcyclic edgeweighted digraphs Q. Suppose that an edgeweighted digraph has no directed cycles. Is it easier to find shortest paths than in a general digraph 1 3 15 5 4 12 3 s 0 8 9 7 2 7 9 6 1 11 5 5 4 13 6 4 20 A. Yes 36Acyclic shortest paths demo Consider vertices in topological order. Relax all edges pointing from that vertex. 0→1 5.0 1 3 15 0→4 9.0 5 0→7 8.0 4 12 1→2 12.0 3 s 0 1→3 15.0 8 9 7 1→7 4.0 2 7 2→3 3.0 9 6 1 2→6 11.0 11 5 3→6 9.0 5 4→5 4.0 4 13 4→6 20.0 6 4 4→7 5.0 20 5→2 1.0 5→6 13.0 an edgeweighted DAG 7→5 6.0 7→2 7.0 37Acyclic shortest paths demo Consider vertices in topological order. Relax all edges pointing from that vertex. 0 1 4 7 5 2 3 6 1 3 v distTo edgeTo 0 0.0 1 5.0 0→1 s 0 2 14.0 5→2 7 2 3 17.0 2→3 4 9.0 0→4 5 13.0 4→5 5 6 25.0 2→6 7 8.0 0→7 6 4 shortestpaths tree from vertex s 38Shortest paths in edgeweighted DAGs Proposition. Topological sort algorithm computes SPT in any edge weighted DAG in time proportional to E + V. edge weights can be negative Pf. Each edge e = v→w is relaxed exactly once (when vertex v is relaxed), leaving distTow ≤ distTov + e.weight(). Inequality holds until algorithm terminates because: distTo values are monotone decreasing – distTow cannot increase – distTov will not change because of topological order, no edge pointing to v will be relaxed after v is relaxed Thus, upon termination, shortestpaths optimality conditions hold. 39Shortest paths in edgeweighted DAGs public class AcyclicSP private DirectedEdge edgeTo; private double distTo; public AcyclicSP(EdgeWeightedDigraph G, int s) edgeTo = new DirectedEdgeG.V(); distTo = new doubleG.V(); for (int v = 0; v G.V(); v++) distTov = Double.POSITIVEINFINITY; distTos = 0.0; Topological topological = new Topological(G); topological order for (int v : topological.order()) for (DirectedEdge e : G.adj(v)) relax(e); 40Contentaware resizing Seam carving. Avidan and Shamir Resize an image without distortion for display on cell phones and web browsers. http://www.youtube.com/watchv=vIFCV2spKtg 41Contentaware resizing Seam carving. Avidan and Shamir Resize an image without distortion for display on cell phones and web browsers. In the wild. Photoshop CS 5, Imagemagick, GIMP, ... 42Contentaware resizing To find vertical seam: Grid DAG: vertex = pixel; edge = from pixel to 3 downward neighbors. Weight of pixel = energy function of 8 neighboring pixels. Seam = shortest path (sum of vertex weights) from top to bottom. 43Contentaware resizing To find vertical seam: Grid DAG: vertex = pixel; edge = from pixel to 3 downward neighbors. Weight of pixel = energy function of 8 neighboring pixels. Seam = shortest path (sum of vertex weights) from top to bottom. seam 44Contentaware resizing To remove vertical seam: Delete pixels on seam (one in each row). seam 45Contentaware resizing To remove vertical seam: Delete pixels on seam (one in each row). 46Longest paths in edgeweighted DAGs Formulate as a shortest paths problem in edgeweighted DAGs. Negate all weights. equivalent: reverse sense of equality in relax() Find shortest paths. Negate weights in result. longest paths input shortest paths input 54 0.35 54 0.35 47 0.37 47 0.37 57 0.28 57 0.28 54 0.35 s 51 0.32 51 0.32 47 0.37 40 0.38 40 0.38 57 0.28 02 0.26 02 0.26 51 0.32 37 0.39 37 0.39 40 0.38 13 0.29 13 0.29 02 0.26 72 0.34 72 0.34 37 0.39 62 0.40 62 0.40 13 0.29 36 0.52 36 0.52 72 0.34 60 0.58 60 0.58 64 0.93 64 0.93 62 0.40 36 0.52 60 0.58 64 0.93 Key point. Topological sort algorithm works even with negative weights. 47Longest paths in edgeweighted DAGs: application Parallel job scheduling. Given a set of jobs with durations and precedence constraints, schedule the jobs (by finding a start time for each) so as to achieve the minimum completion time, while respecting the constraints. must complete job duration before 0 41.0 1 7 9 1 51.0 2 2 50.0 3 36.0 4 38.0 1 5 45.0 7 3 6 21.0 3 8 0 9 6 8 2 7 32.0 3 8 5 4 8 32.0 2 9 29.0 4 6 0 41 70 91 123 173 A job scheduling problem Parallel job scheduling solution 48Critical path method CPM. To solve a parallel jobscheduling problem, create edgeweighted DAG: Source and sink vertices. must complete job duration before Two vertices (begin and end) for each job. 0 41.0 1 7 9 1 51.0 2 Three edges for each job. 2 50.0 – begin to end (weighted by duration) 3 36.0 4 38.0 – source to begin (0 weight) 5 45.0 6 21.0 3 8 – end to sink (0 weight) 7 32.0 3 8 8 32.0 2 One edge for each precedence constraint (0 weight). 9 29.0 4 6 A job scheduling problem job start job finish precedence constraint 51 (zero weight) 1 1 41 0 0 50 2 2 32 32 duration 7 7 8 8 zeroweight zeroweight edge from each edge to each 21 36 6 6 job start 3 3 job finish 29 9 9 38 4 4 45 5 5 Edgeweighted DAG representation of job scheduling 49Critical path method CPM. Use longest path from the source to schedule each job. 1 7 3 0 9 6 8 2 5 4 0 41 70 91 123 173 Parallel job scheduling solution 51 1 1 41 0 0 50 2 2 32 32 duration 7 7 8 8 critical path 21 36 6 6 3 3 29 9 9 38 4 4 45 5 5 Longest paths solution to job scheduling example 504.4 SHORTEST PATHS APIs ‣ shortestpaths properties ‣ Dijkstra's algorithm ‣ Algorithms edgeweighted DAGs ‣ negative weights ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduShortest paths with negative weights: failed attempts Dijkstra. Doesn’t work with negative edge weights. 6 0 1 Dijkstra selects vertex 3 immediately after 0. 2 8 4 But shortest path from 0 to 3 is 0→1→2→3. 3 3 2 Reweighting. Add a constant to every edge weight doesn’t work. 0 14 1 Adding 8 to each edge weight changes the shortest path from 0→1→2→3 to 0→3. 10 0 12 11 3 2 Conclusion. Need a different algorithm. 52Negative cycles Def. A negative cycle is a directed cycle whose sum of edge weights is negative. digraph 45 0.35 s 54 0.66 47 0.37 57 0.28 75 0.28 51 0.32 04 0.38 02 0.26 73 0.39 13 0.29 negative cycle (0.66 + 0.37 + 0.28) 27 0.34 5475 62 0.40 36 0.52 shortest path from 0 to 6 60 0.58 0475475...136 64 0.93 An edgeweighted digraph with a negative cycle Proposition. A SPT exists iff no negative cycles. assuming all vertices reachable from s 53BellmanFord algorithm BellmanFord algorithm Initialize distTos = 0 and distTov = ∞ for all other vertices. Repeat V times: Relax each edge. for (int i = 0; i G.V(); i++) for (int v = 0; v G.V(); v++) pass i (relax each edge) for (DirectedEdge e : G.adj(v)) relax(e); 54BellmanFord algorithm demo Repeat V times: relax all E edges. 0→1 5.0 0→4 9.0 0→7 8.0 1 3 1→2 12.0 15 1→3 15.0 5 4 1→7 4.0 12 3 s 0 2→3 3.0 8 9 2→6 11.0 7 2 7 3→6 9.0 9 6 1 4→5 4.0 11 5 4→6 20.0 5 4→7 5.0 4 13 5→2 1.0 6 4 20 5→6 13.0 7→5 6.0 7→2 7.0 an edgeweighted digraph 55BellmanFord algorithm demo Repeat V times: relax all E edges. 1 3 v distTo edgeTo 0 0.0 1 5.0 0→1 s 0 2 14.0 5→2 7 2 3 17.0 2→3 4 9.0 0→4 5 13.0 4→5 5 6 25.0 2→6 7 8.0 0→7 6 4 shortestpaths tree from vertex s 56BellmanFord algorithm: visualization passes 4 7 10 13 SPT BellmanFord (250 vertices) 57BellmanFord algorithm: analysis BellmanFord algorithm Initialize distTos = 0 and distTov = ∞ for all other vertices. Repeat V times: Relax each edge. Proposition. Dynamic programming algorithm computes SPT in any edge weighted digraph with no negative cycles in time proportional to E × V. Pf idea. After pass i, found path that is at least as short as any shortest path containing i (or fewer) edges. 58BellmanFord algorithm: practical improvement Observation. If distTov does not change during pass i, no need to relax any edge pointing from v in pass i+1. FIFO implementation. Maintain queue of vertices whose distTo changed. be careful to keep at most one copy of each vertex on queue (why) Overall effect. The running time is still proportional to E × V in worst case. But much faster than that in practice. 59Single source shortestpaths implementation: cost summary algorithm restriction typical case worst case extra space no directed topological sort E + V E + V V cycles Dijkstra no negative E log V E log V V weights (binary heap) BellmanFord E V E V V no negative no negative cycles cycles BellmanFord E + V E V V (queuebased) Remark 1. Directed cycles make the problem harder. Remark 2. Negative weights make the problem harder. Remark 3. Negative cycles makes the problem intractable. 60Finding a negative cycle Negative cycle. Add two method to the API for SP. boolean hasNegativeCycle() is there a negative cycle Iterable DirectedEdge negativeCycle() negative cycle reachable from s digraph 45 0.35 digraph 54 0.66 45 0.35 s 47 0.37 54 0.66 57 0.28 47 0.37 75 0.28 57 0.28 51 0.32 75 0.28 04 0.38 51 0.32 02 0.26 04 0.38 73 0.39 02 0.26 13 0.29 negative cycle (0.66 + 0.37 + 0.28) 73 0.39 27 0.34 13 0.29 5475 negative cycle (0.66 + 0.37 + 0.28) 62 0.40 27 0.34 5475 36 0.52 62 0.40 shortest path from 0 to 6 60 0.58 36 0.52 0475475...136 shortest path from 0 to 6 64 0.93 60 0.58 0475475...136 64 0.93 An edgeweighted digraph with a negative cycle An edgeweighted digraph with a negative cycle 61Finding a negative cycle Observation. If there is a negative cycle, BellmanFord gets stuck in loop, updating distTo and edgeTo entries of vertices in the cycle. s 6 3 4 2 edgeTov 1 5 v Proposition. If any vertex v is updated in pass V, there exists a negative cycle (and can trace back edgeTov entries to find it). In practice. Check for negative cycles more frequently. 62Negative cycle application: arbitrage detection Problem. Given table of exchange rates, is there an arbitrage opportunity USD EUR GBP CHF CAD USD 1 0.741 0.657 1.061 1.011 EUR 1.350 1 0.888 1.433 1.366 GBP 1.521 1.126 1 1.614 1.538 CHF 0.943 0.698 0.620 1 0.953 CAD 0.995 0.732 0.650 1.049 1 Ex. 1,000 ⇒ 741 Euros ⇒ 1,012.206 Canadian dollars ⇒ 1,007.14497. 1000 × 0.741 × 1.366 × 0.995 = 1007.14497 631.433 0.698 1.011 0.995 0.888 1.126 1.061 0.943 Negative cycle application: arbitrage detection Currency exchange graph. Vertex = currency. Edge = transaction, with weight equal to exchange rate. Find a directed cycle whose product of edge weights is 1. 0.741 1.366 .995 = 1.00714497 EUR 0.657 USD GBP 1.521 1.049 CAD CHF 0.953 An arbitrage opportunity Challenge. Express as a negative cycle detection problem. 64 0.741 1.350 0.650 1.538 0.732 1.366 0.620 1.614.3598 .3595 .0109 .0050 .1188 .1187 .0592 .0587 Negative cycle application: arbitrage detection Model as a negative cycle detection problem by taking logs. Let weight of edge v→w be ln (exchange rate from currency v to w). Multiplication turns to addition; 1 turns to 0. Find a directed cycle whose sum of edge weights is 0 (negative cycle). ln(.741) ln(1.366) ln(.995) EUR .2998 .3119 + .0050 = .0071 .4201 USD GBP .4914 replace each weight w with ln(w) .0478 CAD CHF .0481 A negative cycle that represents an arbitrage opportunity Remark. Fastest algorithm is extraordinarily valuable 65 .2998 .3001 .4308 .4305 .3120 .3119 .4780 .4787Shortest paths summary Nonnegative weights. Arises in many application. Dijkstra's algorithm is nearly lineartime. Acyclic edgeweighted digraphs. Arise in some applications. Topological sort algorithm is linear time. Edge weights can be negative. Negative weights and negative cycles. Arise in some applications. If no negative cycles, can find shortest paths via BellmanFord. If negative cycles, can find one via BellmanFord. Shortestpaths is a broadly useful problemsolving model. 66
Website URL
Comment