Comment

Comment by tylerhou

It 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/

parent tylerhou 3 years ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton