Subhash Suri UC Santa BarbaraCS-230bAdvanced Algorithms andApplicationsSubhash SuriComputer Science DepartmentUC Santa BarbaraFall Quarter 2004.Subhash Suri UC Santa BarbaraShortest Pathsu vs101572 3xy296• Find shortest length path from s to v?• s → x → u → v has length 5 + 3 + 1 = 9.• Many applications. Discussed later.• A network G = (V, E).• Vertices (nodes) V = {1, . . . , n}.• Edges (links) E = {e1, e2, . . . , em}. Edgeeij= (i, j) is directed from i to j.• Edge eijhas cost (weight) cij. The costscan be positive or negative!Subhash Suri UC Santa BarbaraNegative Cost ShortestPathsvsxy76259−3−4−28 7u• What’s the shortest path from s to y?• s → x → v → u → y has length −2.• How can costs be negative?• Examples later. (Arbitrage trading,scientific simulations, matchingalgorithms, min cost network flows).• More general the formulation, the better.• Any simple way to eliminate negativeedges? Adding a constant to all edges?Subhash Suri UC Santa BarbaraGetting Startedu vs101572 3xy296• Source node s = v0.• Compute SP distances from s to everynode vj.• The paths themselves can be recoveredfrom predecessors.• Distance labels d(j): best path length to jfound so far.• Initially, d(0) = 0, and d(j) = ∞ for others.• The algorithm improves estimates for alld(j) until SP distances become known.Subhash Suri UC Santa BarbaraBasic Idea• How to improve the distance estimate?sciji j507510• Suppose there is an edge (i, j) such thatd(j) > d(i) + cijthen we can improve the estimate of d(j):d(j) = d(i) + cij• Previously, d(i) = 50 and d(j) = 75. Therelabeling step finds a better path to j viai of cost 60.Subhash Suri UC Santa BarbaraOptimality ConditionTheorem: Suppose each d(j) is the length ofsome feasible path from s to j. Then, thesed() distances are shortest path distance if andonly ifd(j) ≤ d(i) + cij, for all(i, j) ∈ Eu vs101572 3xy29608957Necessity Proof: Suppose ∃ an edge (i, j)violating the condition. Then,d(j) > d(i) + cij. But then we can reach j viai at cost d(i) + cij, which is smaller than d(j),contradicting the d(j) is shortest pathdistance.Subhash Suri UC Santa BarbaraSufficiencys12k−1kccc01 12k−1,k1. Suppose d(j) ≤ d(i) + cijholds.2. Let k be a node with incorrect distance.3. s → 1 → 2 · · · k − 1 → k be actual SP.4. So, c01+ c12+ · · · + ck−1,k< d(k). (∗)5. By optimality condition we haved(k) ≤ d(k − 1) + ck−1,kd(k − 1) ≤ d(k − 2) + ck−2,k−1...d(1) ≤ d(0) + c016. By summing, d(k) ≤ c01+ c12+ · · · + ck−1,kwhich contradicts (∗)!!!.Subhash Suri UC Santa BarbaraGeneric SP Algorithmalgorithm Label-Correcting1. d(s) = 0, pred(s) = 0;2. d(j) = ∞, for j = 1, 2, . . . , n.3. while ∃(i, j) with d(j) > d(i) + cijdo4. d(j) = d(i) + cij;5. pred(j) = i;6. end;• Run the algorithm on example.u vs101572 3xy296Subhash Suri UC Santa BarbaraAnalysis• By optimality theorem, the output iscorrect IF the algorithm halts.• If costs are integers, each distance updatechanges the value by ≥ 1.• If the largest edge cost is |C|, then SPlength cannot drop below −nC. Thelargest feasible path length is +nC.• Total number of relabeling is at most n2C.• So, the algorithm halts, although C can bevery large. Algorithm not stronglypolynomial.• Alternatively, one can bound the run timeby O(2n).Subhash Suri UC Santa BarbaraSelf-Study• Construct bad examples for genericlabeling algorithm.• Show termination even when costs arenon-integer.• Prove upper bound of O(2n).Subhash Suri UC Santa BarbaraImproved Label-Correcting• The Generic Label-Correcting does notspecify any order for selecting edgeviolations.• To improve running time, we need abetter order.• Many variants of this algorithm, withdifferent complexity and performance.• Bellman-Ford Method: elegant, admitssimple analysis, works very well inpractice, and has the best theoreticalrunning time.Subhash Suri UC Santa BarbaraBellman-Ford Algorithmalgorithm Bellman-FordInput: Graph G = (V, E), with source node s.1. d(s) = 0, pred(s) = 0;2. d(j) = ∞, for j = 1, 2, . . . , n.3. for k = 1 to |V | − 1 do4. for each edge (i, j) in E do5. if d(j) > d(i) + cij;6. d(j) = d(i) + cij;7. pred(j) = i;8. end;Subhash Suri UC Santa BarbaraExamplesuv58−6• Use edge order (v, u), (s, u), (s, v).Subhash Suri UC Santa BarbaraBellman-Ford: Correctnesssuv58−61. The algorithm terminates after O(nm)steps, by construction. (Key: SP has ≤ nedges.)2. Show that distances computed are correct.3. By Induction. If the SP to a node j consists ofk edges, then after k iterations of the outer loop,d(j) is correct.4. Basis of induction: k = 1. If the shortestpath to j has only one edge, then E mustcontain this edge (s, j). During the k = 1iteration, the inner loop scans this edge atsome point, and updates the distance d(j)correctly.Subhash Suri UC Santa BarbaraBellman-Ford: CorrectnessGeneral Case of Induction:i1i2ikik−1sj• Suppose, by IH, that after k − 1 iterations,nodes whose SP use at most k − 1 edgesare correctly labeled.• Consider a node j whose SP path hasexactly k edges. Lets → i1→ i2· · · ik−1→ ik= j be the SP to j.• By induction, d(ik−1) is correct.• When the edge (ik−1, j) is scanned, duringthe kth iteration of outer loop, we updated(j) ← d(ik−1) + cik−1,j.• So, d(j) is correct after k iterations.Subhash Suri UC Santa BarbaraNegative Edges and Cycles1. Effect of negative costs on Bellman-Ford?2. The optimality condition is bullet-proof.3. What about the termination condition?4. Suppose G contains a cycle Z whose totalcost is negative. By repeatedly goingaround Z we can continuously lower thepath length!5. Theorem: SP distances in G are welldefined if and only if G does not containsa negative-cost cycle reachable from s. IfSP are well-defined, then there is always asimple shortest path from s to each j.6. Proof: If all reachable cycles arenon-negative, then we can always cutthem off.7. Consequently, Bellman-Ford halts afterO(nm) steps IF there is no negative cyclereachable from s.Subhash Suri UC Santa BarbaraDetecting Negative Cycles• How to tell if G has a negative cycle?• [Idea 1:] We know that −nC is a lowerbound on any d(). So, if any label dropsbelow −nC, we have a negative cycle. Youcan trace the cycle using pred pointers.• [Idea 2:] Use the Bellman-Ford algorithm.At the end, make one more pass over alledges E. If you find ANY edge (i, j) forwhich d(j) > d(i) + cij, then