Computer Science & Engineering 423/823 Design And

CSCE423/823IntroductionBellman-FordAlgorithmSSSPs inDirectedAcyclic GraphsComputer Science & Engineering 423/823Design and Analysis of AlgorithmsLecture 05 — Single-Source Shortest Paths (Chapter 24)Dijkstra’sAlgorithmDifferenceConstraintsand ShortestPaths1 / 36Stephen Scott(Adapted from Vinodchandran N. Variyam)

ture ofa Shortest rdAlgorithmSSSPs inDirectedAcyclic d ShortestPaths2 / 36Given a weighted, directed graph G (V, E) with weight functionw:E RThe weight of path p hv0 , v1 , . . . , vk i is the sum of the weights ofits edges:kXw(vi 1 , vi )w(p) i 1Then the shortest-path weight from u to v is pmin{w(p) : uv} if there is a path from u to vδ(u, v) otherwiseA shortest path from u to v is any path p with weightw(p) δ(u, v)Applications: Network routing, driving directions

Types of Shortest Path ProblemsCSCE423/823Given G as described earlier,IntroductionOptimalSubstructure ofa Shortest rdAlgorithmSSSPs inDirectedAcyclic d ShortestPaths3 / 36Single-Source Shortest Paths: Find shortest paths from sourcenode s to every other nodeSingle-Destination Shortest Paths: Find shortest paths from everynode to destination tCan solve with SSSP solution. How?Single-Pair Shortest Path: Find shortest path from specific node uto specific node vCan solve via SSSP; no asymptotically faster algorithm knownAll-Pairs Shortest Paths: Find shortest paths between every pair ofnodesCan solve via repeated application of SSSP, but can do better

Optimal Substructure of a Shortest PathCSCE423/823IntroductionOptimalSubstructure ofa Shortest rdAlgorithmSSSPs inDirectedAcyclic d ShortestPaths4 / 36The shortest paths problem has the optimal substructure property:If p hv0 , v1 , . . . , vk i is a SP from v0 to vk , then for 0 i j k,pij hvi , vi 1 , . . . , vj i is a SP from vi to vjp0ipijpjkProof: Let p v0vivjvk with weightw(p) w(p0i ) w(pij ) w(pjk ). If there exists a path p0ij from vi tovj with w(p0ij ) w(pij ), then p is not a SP sincev0p0ivip0ijvjpjkvk has less weight than pThis property helps us to use a greedy algorithm for this problem

Negative-Weight Edges (1)CSCE423/823IntroductionOptimalSubstructure ofa Shortest rdAlgorithmSSSPs inDirectedAcyclic d ShortestPaths5 / 36What happens if the graph G has edges with negative weights?Dijkstra’s algorithm cannot handle this, Bellman-Ford can, under theright circumstances (which circumstances?)

Negative-Weight Edges (2)CSCE423/823IntroductionOptimalSubstructure ofa Shortest rdAlgorithmSSSPs inDirectedAcyclic d ShortestPaths6 / 36

CyclesCSCE423/823IntroductionOptimalSubstructure ofa Shortest rdAlgorithmSSSPs inDirectedAcyclic d ShortestPaths7 / 36What kinds of cycles might appear in a shortest path?Negative-weight cycleZero-weight cyclePositive-weight cycle

re ofa Shortest rdAlgorithmSSSPs inDirectedAcyclic d ShortestPaths8 / 36Given weighted graph G (V, E) with source node s V and othernode v V (v 6 s), we’ll maintain d[v], which is upper bound onδ(s, v)Relaxation of an edge (u, v) is the process of testing whether wecan decrease d[v], yielding a tighter upper bound

Initialize-Single-Source(G, s)CSCE423/823IntroductionOptimalSubstructure ofa Shortest rdAlgorithmSSSPs inDirectedAcyclic Graphs1234for each vertex v V dod[v] π[v] nilendd[s] 0Dijkstra’sAlgorithmDifferenceConstraintsand ShortestPaths9 / 36How is the invariant maintained?

Relax(u, v, w)CSCE423/823IntroductionOptimalSubstructure ofa Shortest rdAlgorithm12if d[v] d[u] w(u, v) thend[v] d[u] w(u, v)π[v] u3SSSPs inDirectedAcyclic d ShortestPaths10 / 36How do we know that we can tighten d[v] like this?

Relaxation ExampleCSCE423/823IntroductionOptimalSubstructure ofa Shortest rdAlgorithmSSSPs inDirectedAcyclic d ShortestPaths11 / 36Numbers in nodes are values of d

Bellman-Ford thmIntroductionThe AlgorithmExampleAnalysisSSSPs inDirectedAcyclic d ShortestPaths12 / 36Greedy algorithmWorks with negative-weight edges and detects if there is anegative-weight cycleMakes V 1 passes over all edges, relaxing each edge during eachpass

Bellman-Ford(G, w, troductionThe AlgorithmExampleAnalysis345SSSPs inDirectedAcyclic and ShortestPaths13 / 367Initialize-Single-Source(G, s)for i 1 to V 1 dofor each edge (u, v) E doRelax(u, v, w)endendfor each edge (u, v) E doif d[v] d[u] w(u, v) thenreturn false // G has a negative-wt cycle91011endreturn true // G has no neg-wt cycle reachable frms

Bellman-Ford Algorithm Example roductionThe AlgorithmExampleAnalysisSSSPs inDirectedAcyclic d ShortestPaths14 / 36Within each pass, edges relaxed in this order:(t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)

Bellman-Ford Algorithm Example roductionThe AlgorithmExampleAnalysisSSSPs inDirectedAcyclic d ShortestPaths15 / 36Within each pass, edges relaxed in this order:(t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)

Time Complexity of Bellman-Ford thmIntroductionThe AlgorithmExampleAnalysisSSSPs inDirectedAcyclic d ShortestPaths16 / 36Initialize-Single-Source takes how much time?Relax takes how much time?What is time complexity of relaxation steps (nested loops)?What is time complexity of steps to check for negative-weight cycles?What is total time complexity?

Correctness of Bellman-Ford AlgorithmCSCE423/823Assume no negative-weight nThe AlgorithmExampleAnalysisSSSPs inDirectedAcyclic d ShortestPaths17 / 36Since no cycles appear in SPs, every SP has at most V 1 edgesThen define sets S0 , S1 , . . . S V 1 :Sk {v V : spv s.t. δ(s, v) w(p) and p k}Loop invariant: After ith iteration of outer relaxation loop (Line 2),for all v Si , we have d[v] δ(s, v)Can prove via inductionImplies that, after V 1 iterations, d[v] δ(s, v) for allv V S V 1

Correctness of Bellman-Ford Algorithm (2)CSCE423/823Let c hv0 , v1 , . . . , vk v0 i be neg-weight cycle reachable from he AlgorithmExampleAnalysisSSSPs inDirectedAcyclic d ShortestPaths18 / 36w(vi 1 , vi ) 0i 1If algorithm incorrectly returns true, then (due to Line 8) for allnodes in the cycle (i 1, 2, . . . , k),d[vi ] d[vi 1 ] w(vi 1 , vi )By summing, we getkXi 1d[vi ] kXi 1d[vi 1 ] kXw(vi 1 , vi )i 1PPSince v0 vk , ki 1 d[vi ] ki 1 d[vi 1 ]PkThis implies that 0 i 1 w(vi 1 , vi ), a contradiction

SSSPs in Directed Acyclic GraphsCSCE423/823IntroductionWhy did Bellman-Ford have to run V 1 iterations of edgerelaxations?To confirm that SP information fully propagated to all nodesBellman-FordAlgorithmSSSPs inDirectedAcyclic GraphsIntroductionThe renceConstraintsand ShortestPaths19 / 36What if we knew that, after we relaxed an edge just once, we wouldbe completely done with it?Can do this if G a dag and we relax edges in correct order (whatorder?)

Dag-Shortest-Paths(G, w, s inDirectedAcyclic GraphsIntroductionThe renceConstraintsand ShortestPaths20 / 365topologically sort the vertices of GInitialize-Single-Source(G, s)for each vertex u V , taken in topo sortedorder dofor each v Adj[u] doRelax(u, v, w)end6end1234

SSSP dag Example Ps inDirectedAcyclic GraphsIntroductionThe renceConstraintsand ShortestPaths21 / 36

SSSP dag Example Ps inDirectedAcyclic GraphsIntroductionThe renceConstraintsand ShortestPaths22 / 36

Time Complexity of SSSP in Ps inDirectedAcyclic GraphsIntroductionThe renceConstraintsand ShortestPaths23 / 36Topological sort takes how much time?Initialize-Single-Source takes how much time?How many calls to Relax?What is total time complexity?

Dijkstra’s thmSSSPs inDirectedAcyclic GraphsDijkstra’sAlgorithmIntroductionThe AlgorithmExampleAnalysisDifferenceConstraintsand ShortestPaths24 / 36Faster than Bellman-FordRequires all edge weights to be nonnegativeMaintains set S of vertices whose final shortest path weights from shave been determinedRepeatedly select u V \ S with minimum SP estimate, add u to S,and relax all edges leaving uUses min-priority queue

Dijkstra(G, w, s inDirectedAcyclic GraphsDijkstra’sAlgorithmIntroductionThe AlgorithmExampleAnalysisDifferenceConstraintsand ShortestPaths25 / 368Initialize-Single-Source(G, s)S Q Vwhile Q 6 dou Extract-Min(Q)S S {u}for each v Adj[u] doRelax(u, v, w)end9end1234567

Dijkstra’s Algorithm Example Ps inDirectedAcyclic GraphsDijkstra’sAlgorithmIntroductionThe AlgorithmExampleAnalysisDifferenceConstraintsand ShortestPaths26 / 36

Dijkstra’s Algorithm Example Ps inDirectedAcyclic GraphsDijkstra’sAlgorithmIntroductionThe AlgorithmExampleAnalysisDifferenceConstraintsand ShortestPaths27 / 36

Time Complexity of Dijkstra’s AlgorithmCSCE423/823Using array to implement priority queue,IntroductionBellman-FordAlgorithmSSSPs inDirectedAcyclic GraphsDijkstra’sAlgorithmIntroductionThe AlgorithmExampleAnalysisDifferenceConstraintsand ShortestPaths28 / 36Initialize-Single-Source takes how much time?What is time complexity to create Q?How many calls to Extract-Min?What is time complexity of Extract-Min?How many calls to Relax?What is time complexity of Relax?What is total time complexity?Using heap to implement priority queue, what are the answers to theabove questions?When might you choose one queue implementation over another?

Correctness of Dijkstra’s thmSSSPs inDirectedAcyclic GraphsDijkstra’sAlgorithmIntroductionThe AlgorithmExampleAnalysisDifferenceConstraintsand ShortestPaths29 / 36Invariant: At the start of each iteration of the while loop,d[v] δ(s, v) for all v SProve by contradiction (p. 660)Since all vertices eventually end up in S, get correctness of thealgorithm

Linear rithmSSSPs inDirectedAcyclic d s andFeasibilityConstraintGraphsSolvingFeasibility withBellman-Ford30 / 36Given an m n matrix A and a size-m vector b Pand a size-n vectorc, find a vector x of n elements that maximizes ni 1 ci xi subject toAx b 2211 E.g. c 2 3 , A 1 2 , b 4 implies: 8 1 0maximize 2x1 3x2 subject tox1 x2 22x1 2x2 4x1 8Solution: x1 16, x2 6

Difference Constraints and rithmSSSPs inDirectedAcyclic d s andFeasibilityConstraintGraphsSolvingFeasibility withBellman-Ford31 / 36Decision version of this problem: No objective function tomaximize; simply want to know if there exists a feasible solution,i.e. an x that satisfies Ax bSpecial case is when each row of A has exactly one 1 and one 1,resulting in a set of difference constraints of the formxj xi bkApplications: Any application in which a certain amount of timemust pass between events (x variables represent times of events)

Difference Constraints and Feasibility (2)CSCE423/823Introduction Bellman-FordAlgorithmSSSPs inDirectedAcyclic d s andFeasibilityConstraintGraphsSolvingFeasibility withBellman-Ford32 / 36 A 1 1 000 1000 1 0100 1 1 0100 and b 1 0010 00 1 10 00 1 01 000 1 10 1154 1 3 3

Difference Constraints and Feasibility Ps inDirectedAcyclic d s andFeasibilityConstraintGraphsSolvingFeasibility withBellman-Ford33 / 36Is there a setting for x1 , . . . , x5 satisfying:x1 x2 0x1 x5 1x2 x5 1x3 x1 5x4 x1 4x4 x3 1x5 x3 3x5 x4 3One solution: x ( 5, 3, 0, 1, 4)

Constraint SSSPs inDirectedAcyclic d s andFeasibilityConstraintGraphsSolvingFeasibility withBellman-Ford34 / 36Can represent instances of this problem in a constraint graphG (V, E)Define a vertex for each variable, plus one more: If variables arex1 , . . . , xn , get V {v0 , v1 , . . . , vn }Add a directed edge for each constraint, plus an edge from v0 toeach other vertex:E {(vi , vj ) : xj xi bk is a constraint} {(v0 , v1 ), (v0 , v2 ), . . . , (v0 , vn )}Weight of edge (vi , vj ) is bk , weight of (v0 , v ) is 0 for all 6 0

Constraint Graph mSSSPs inDirectedAcyclic d s andFeasibilityConstraintGraphsSolvingFeasibility withBellman-Ford35 / 36