Question? Leave a message!




shortest-paths properties and Algorithms

shortest-paths properties and Algorithms
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Website URL
Comment
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 4.4 SHORTEST PATHS APIs ‣ shortest-paths properties ‣ Dijkstra's algorithm ‣ Algorithms FOUR TH EDITION edge-weighted DAGs ‣ negative weights ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduShortest paths in an edge-weighted digraph Given an edge-weighted digraph, find the shortest path from s to t. edge-weighted digraph 4-5 0.35 5-4 0.35 4-7 0.37 5-7 0.28 7-5 0.28 5-1 0.32 0-4 0.38 0-2 0.26 7-3 0.39 shortest path from 0 to 6 1-3 0.29 0-2 0.26 2-7 0.34 2-7 0.34 6-2 0.40 7-3 0.39 3-6 0.52 3-6 0.52 6-0 0.58 6-4 0.93 An edge-weighted 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/Seam_carving 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. Source-sink: 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 ‣ shortest-paths properties ‣ Dijkstra's algorithm ‣ Algorithms edge-weighted 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; 8Edge-weighted digraph API public class public class EdgeWeightedDigraph EdgeWeightedDigraph EdgeWeightedDigraph(int V) EdgeWeightedDigraph(int V) edge-weighted digraph with V vertices EdgeWeightedDigraph(In in) EdgeWeightedDigraph(In in) edge-weighted 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 self-loops and parallel edges. 9Edge-weighted digraph: adjacency-lists 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 Edge-weighted digraph representation 10Edge-weighted digraph: adjacency-lists 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; 11Single-source 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(); 12Single-source 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): 0-4 0.38 4-5 0.35 5-1 0.32 0 to 2 (0.26): 0-2 0.26 0 to 3 (0.99): 0-2 0.26 2-7 0.34 7-3 0.39 0 to 4 (0.38): 0-4 0.38 0 to 5 (0.73): 0-4 0.38 4-5 0.35 0 to 6 (1.51): 0-2 0.26 2-7 0.34 7-3 0.39 3-6 0.52 0 to 7 (0.60): 0-2 0.26 2-7 0.34 134.4 SHORTEST PATHS APIs ‣ shortest-paths properties ‣ Dijkstra's algorithm ‣ Algorithms edge-weighted DAGs ‣ negative weights ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduData structures for single-source shortest paths Goal. Find the shortest path from s to every other vertex. Observation. A shortest-paths tree (SPT) solution exists. Why? Consequence. Can represent the SPT with two vertex-indexed 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 5-1 0.32 1.05 1 5-1 0.32 1.05 2 0-2 0.26 0.26 2 0-2 0.26 0.26 3 7-3 3 7-3 0.37 0.37 0.97 0.97 4 0-4 0.38 0.38 4 0-4 0.38 0.38 5 4-5 0.35 0.73 5 4-5 0.35 0.73 6 3-6 0.52 1.49 6 3-6 0.52 1.49 7 2-7 0.34 0.60 7 2-7 0.34 0.60 Shortest paths data structures shortest-paths tree from 0 parent-link representation Shortest paths data structures 15Data structures for single-source shortest paths Goal. Find the shortest path from s to every other vertex. Observation. A shortest-paths tree (SPT) solution exists. Why? Consequence. Can represent the SPT with two vertex-indexed 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; 18Shortest-paths optimality conditions Proposition. Let G be an edge-weighted 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 19Shortest-paths optimality conditions Proposition. Let G be an edge-weighted 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 k-1 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 20