3 ms·
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 simpl
by jhuckestein 14y ago
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
- 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.