Hacker News Reader

Well if you're going to have negatively weighted vertices, Dijkstra's algorithm is out of the picture from the start :)

Depending on your use-case, you can often just add the value of the largest negative edge weight (pair of vertices, not a vertex) to all weights and use a simple algorithm like Dijkstra

Interesting- thanks! In what cases can't we do that? (ie. why did Ford and Bellman bother at all?)

In a use case where you don't actually need a shortest path?

Or if you know the path will be a constant numbers of edges, I guess, otherwise adding weights would bias the algorithm toward fewer hops.

Reply on news.ycombinator.com