To Dwight's (I've met him a few times, too. He actually seems like a clever guy) credit, it sounds like he said Dijkstra ;) Just goes to show how little the producers of the show care about the "techy stuff".

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.

>One assumes he's the one shouting "Negative cycles? Bellmans algorithm or Dyson's?!"

I'm assuming he's talking about shortest-path algorithms here (and actually referring to the Ford-Bellman algorithm)— anyone have info about the Dyson algorithm he's referring to?

Never heard of it and googling wields nothing.

I assume he was thinking of Dijkstra's algorithm.

I assume he crossed Dijkstra's algorithm with the Dyson sphere.