3 ms·
Finally, a Fast Algorithm for Shortest Paths on Negative Graphs
- mwint 4y agoCan anyone explain why naively adding cost to every link in the graph doesn’t work? I.e if my graph had costs ranging from -10 to +10, I would add 11 to each and now the costs are +1 to +21… why doesn’t that work? Obviously it must not, but I’m struggling to understand why.
- tylerhou 4y agoIt doesn't preserve the ordering of paths with different lengths. Suppose your bias is B. A length k path will get k*B added to its cost, while a length k+1 path will get (k+1)*B added. That will probably change the ordering of paths. But your idea is not too far off a technique used in the paper. Instead of adding a weight to each edge, the technique is to add a weight to each vertex (call this phi(v)) and modify each edge (u, v)'s weight to w(u, v) + phi(u) - phi(v). It turns out that modifying each edge's weight in this way preserves the ordering of paths. The tricky part is to find a phi that makes every edge weight positive so you can apply Dijkstra's. The above technique -- called "price functions" -- has been known from 1977. The main result of this paper is how to discover price functions very quickly (in ~O(m \log W) time). This requires low-diameter graph decomposition and some other clever combinatorial techniques. Sidenote: just yesterday this algorithm was taught in Berkeley's CS270 class. That's how I know this :). https://www2.eecs.berkeley.edu/Courses/CS270/ https://www2.eecs.berkeley.edu/Courses/CS270/
- bhrgunatha 4y agoThat's odd. I was sure Berkeley provided access to course material to the public.