Yes, he said Dijkstra. He's a FoaF, the mutual friend is a coworker of mine, and this was the topic du jour in one of our IRC channels this afternoon. The context for the discussion was trying to determine whether he was too drunk to math, or needed another drink.

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.