3 ms·
Well if you're going to have negatively weighted vertices, Dijkstra's algorithm is out of the picture from the start :)
by GuiA 14y ago
Well 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.