4 ms·
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 pro
by jhuckestein 14y ago
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".
- GuiA 14y agoWell if you're going to have negatively weighted vertices, Dijkstra's algorithm is out of the picture from the start :)
- jhuckestein 14y agoDepending 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
- GuiA 14y agoInteresting- thanks! In what cases can't we do that? (ie. why did Ford and Bellman bother at all?)
- Evbn 14y agoIn 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.
- rosser 14y agoYes, 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.