Computing Shortest Paths in Graphs with Negative Edges
Learn how to compute all pair shortest paths in graphs with negative edges using a potential function to find feasible potentials, and running Dijkstra from every vertex. Explore methods like Bellman-Ford and using an artificial source to handle negative cycles and unreachable vertices efficiently.
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
All pair shortest paths (APSP) We want to compute the distance between every pair of vertices Output is a matrix ?, ???= ?(?,?) For the shortest paths themselves we also compute a matrix , ??= ? iff (?,?) is in the shortest path tree rooted by ?
Dijkstra from every vertex If there are no negative edges we can just run Dijkstra from every vertex ? ? ?log? + ? What do we do if there are negative edges (but no negative cycles) ?
Use a potential function ???,? = ? ?,? + ? ? ?(?) ?, this preserves shortest paths Find ? for which ???,? 0 ?,? (feasible) and then run Dijkstra from every vertex..
The basics of potentials Thm: Let ???,? = ? ?,? + ? ? ? ? for some ?. Let ? be a path from ? to ?, then ??? = ? ? + ? ? ? ? . In particular, ? is shortest by ? iff it is shortest by ??.
Proof ? s ?1 ? ?? 1 ? 1????,??+1 = ? ?0,?1 + ? ?0 ? ?1+ ??? = ?=0 ? ?1,?2 + ? ?1 ? ?2 + ? ?2,?3 + ? ?2 ? ?3 + + ? ?? 1,?? + ? ?? 1 ? ?? = ? ? + ? ? ? ?
Feasible potential How to find ? such that ???,? 0 ?,? ?
Use Bellman-Ford Pick some arbitrary vertex ? ? Run BF from ? Set ? ? = ? ?,? v u
Problems There may be vertices unreachable from ?
Use an artificial source Add a new vertex ? Add ?,? ? ?, ? ?,? = 0 0 u 0 s
Use an artificial source In ? every ? ? is reachable from ? a negative cycle reachable from ? in ? iff a negative cycle in ? 0 u 0 ? s ?
