Negative Cycles and Shortest Paths in Algorithms
Explore the concept of negative cycles in algorithms and their impact on finding shortest paths. Learn about potential functions, modified weight functions, and Goldberg's algorithm in dealing with negative cycles in directed graphs. Discover how scaling techniques can be used to address negative cycles effectively.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Analysis of Algorithms Shortest Paths - Finding Negative Cycles Uri Zwick Tel Aviv University November 2015 Last modified: December 5, 2017 1
Single Source Shortest Paths Non-negative edge weights ?(? + ?log?) [Dijkstra (1959)] [Fredman-Tarjan (1987)] Undirected positively weighted graphs (word-RAM model) ?(? + ?) [Thorup (1999)] Positive and negative edge weights ?(??) [Bellman (1956)] [Ford-Fulkerson (1962)] Positive and negative integer edge weights ?(? ?log?) [Goldberg (1995)] All edge weights are integral and ?. (? 2.) 2
Potentials and modified weights A function ?:? is called a potential function. If ?:? is a weight (length) function, then the modified weight function ??:? is defined as follows: ???,? = ? ?,? + ? ? ?(?) , ?,? ? Lemma: (i) If ? is a path from ? to ?, then ??? = ? ? + ? ? ?(?). (ii) If ? is a directed cycle, then ??? = ?(?). Corollary: Shortest paths with respect to ?? are also shortest paths with respect to ?. 3
Potentials and negative cycles Theorem: A digraph ? = ?,?,? has no negative cycles if and only if there is a potential function ? such that ???,? = ? ?,? + ? ? ?(?) 0, for every ?,? ?. If there is such an admissible potential function, then by part (ii) of the previous lemma, there are no negative cycles. Suppose that there are no negative cycles. Add a vertex ? and an edge (?,?) of weight 0 for each ? ?. As there are still no negative cycles, distances from ? are well-defined and satisfy the triangle inequality. Let ? ? = ? ?,? = distance from ? to ?. ? ?,? ? ?,? + ?(?,?) , ?,? ? ???,? = ? ?,? + ? ?,? ? ?,? 0 , ?,? ?
Scaling We want to solve a problem with a given integer weight function ?:? Define a coarser integer weight function ? :? ?(?) 2 ? ? = , ? ?. Solve the problem (recursively) with respect to ? . Convert the solution for ? into a solution for ?. 5
Scaling and negative cycles Given a digraph ? = ?,?,? , where ?:? , find a negative cycle, or find a potential function ? such that ??? 0, for every ? ?. ?(?) 2 Let ? ? = , ? ?. A negative cycle with respect to ? is also a negative cycle with respect to ?. Otherwise, let ? :? be such that ?? Let ? ? = 2? (?) , ? ?. ? 0, ? ?. ???,? = ? ?,? + ? ? ? ? 2? ?,? 1 + 2? ? 2? ? 1 We thus only need to consider the case ? ? 1 , ? ?. 6
Goldbergs algorithm Let ? = ?,?,? , where ?:? { 1,0,1, }. Let ? = ?,? ,? , where ? = ? ? ? ? 0}. If a strongly connected component of ? contains a negative edge, then a negative cycle in ? is easily found. Otherwise, contract each strongly connected component of ? . The contracted graph is acyclic. Add a source vertex ? to ? and connect it with 0-edges to all vertices of ? . Compute the distances ? ?,? , for all ? ?. Can be done in ? ? time as ? is acyclic. Let ??= ? ? ? ?,? = ?}. 7
Goldbergs algorithm Layers: ??= ? ? ? ?,? = ?}. ? ?,? = 0 , ? ??, ? ?? ? ? ? ?,? = 1 , ? ??, ? ?? ? < ? s 1 0 2 8 ?0 ?1 ?2 ??
Dilworths theorem Let ? be the index of the last layer. Let ? be the number of negative vertices, i.e., vertices with an incoming negative edge. If ? If ? > ?, there is a layer ??with at least ? negative vertices. ?, there is a path with at least ? negative vertices. s 1 0 9 ?0 ?1 ?2 ??
A layer with negative vertices Suppose that ??contains many (at least ?) negative vertices. Assign the vertices of ?0 ?1 ?? 1a potential of 0. Assign the vertices of ?? ??+1 ??a potential of 1. Vertices of ??are no longer negative. No negative vertices introduced. There are new 0 edges. Need to recompute ? . s 1 0 1 1 10 ?0 ?1 ?? ??
A path with negative vertices 1 ?3 0 1 1 0 1 0 2 ?3 ?1 ?2 Let ?3be the set of vertices reachable from ?3by 0 and 1 edges. (As ? is acyclic, ?3is the only vertex on the path in ?3.) (We cannot reach 1 edges if the path is maximal .) Decrease the potential of all vertices in ?3by 1. ?3is no longer negative. No new negative vertices. But, there are new 0 edges. 11
A path with negative vertices 0 ?1 ?3 ?2 0 1 1 0 0 0 1 ?3 ?1 ?2 Let ?2be the set of vertices reachable from ?2by 0 and 1 edges. If ?2contains a vertex preceding ?2on the path negative cycle. Decrease the potential of all vertices in ?2by 1. (Vertices in ?3have their potential decreased by 2.) 12
A path with negative vertices Let ?1,?2, ,??be the negative vertices on the path. For ? = ?,? 1, ,1 do: Let ??be the vertices reachable from ??by 0 and 1 edges. If ??contains a vertex preceding ??on the path, or if a path to ?? containing at least one 1 edge is discovered negative cycle. Decrease the potential of all the vertices in ??by 1. (This may create new 0 edges emanating from vertices of ??.) Claim: If no negative cycles are discovered, then: (i) ?1,?2, ,??are no longer negative. (ii) No new negative vertices introduced. (iii) No edge weight drops below 1. Exercise 1: Prove the above claim. Exercise 2: Implement the process above in ? ? time. (We will essentially solve these exercise below. Try to do it directly.)
A path with negative vertices A clever way of implementing the previous process. Let ?+?,? = max 0,?(?,?) . Add a source vertex ?, and edges (?,?), for every ? ?. Let ?+?,?? = ? ?, for 1 ? ?. Let ?+?,? = ?, for ? ? ?1,?2, ,??. Compute the distances ?+? = ?+(?,?) from ? with respect to ?+. Can be done in ?(? + ?) time using Dial s algorithm. Let ? ? = ?+(?) , ? ?. If the graph contains no negative cycles then: (i) ?1,?2, ,??are no longer negative. (ii) No new negative vertices introduced. (iii) No edge weight drops below 1.
A path with negative vertices ? 0 ? 1 ? 2 ? ? ? 0 1 1 1 0 1 0 ?? ?? ? ?1 ?2 ?+?,? = ?(?,?) ?+? ?+? + ?(?,?) ???,? 0 (ii) ? ?,? 0 ?+?,? = 0 ?+? ?+? ???,? 1 (iii) ? ?,? = 1
A path with negative vertices ? ? 1 ? ? 0 ? ? 0 1 1 1 0 1 0 ?? 1 ?? ?1 ?? ? ? ? Suppose that ? ?,?? = 1. If ?+? > ?+(??), then ???,?? = ? ?,?? + ?+? ?+?? 0. Otherwise, ?+? ?+?? ? ?.A shortest path from ? to ? starts with (?,??), where ? ?, and then a path ? from ??to ?. By the triangle inequality, ? ? ?+? = ?+(??,?) ? ?. Let ? be the portion of the path from ??to ??. Clearly ? ? = ? ?. ?,?,(?,??) is a negative cycle. ? ? ? ? + ? ? 1 1.
Dials algorithm [Dial (1969)] Let ? = (?,?,?), where ?:? +. Let ? ?. Let ? = max ? ???(?,?) be the maximum distance from ?. The SSSP from ? can be solved in ?(? + ?) time. Use a bucket-based priority queue to implement Dijkstra. The priority queue used by Dijkstra is monotone. (Keys of extracted items cannot decrease.) 0 1 ? ?
Complexity of Goldbergs algorithm Number of recursive calls is log?. After each recursive call, we adjust the potential, or find a negative cycle, by the process above. If there are ? negative vertices, we get rid of ? of them, without creating new ones, in ?(?) time. How many such iterations, ? ? ?, do we need? If ? 1 4?2, then ? ? <1 As ?0 ? 1 4 Thus, the total runtime is ?(? ?log?). 4? 12. (? ? is increasing.) 2, number of iterations is at most 4?. 4? 18
