Content deleted Content added
No edit summary |
Zero weight cycles |
||
Line 6:
I changed the problem from weighted graph to weighted *digraph* because Bellman Ford fails spectacularly on undirected graphs: If there is a negative weight edge, say {u, v}, then Bellman-Ford will get stuck updating u and v foreover, even if there is no negative weight cycle. This subtlety may be worth mentioning in the main article. To find shortest paths in undirected graphs with negative edge weights, you can reduce the problem to weighted nonbipartite matching.
== Zero weight cycles ==
I seems to me that if a graph has some cycle that weighs zero between start and end, then there could be infinite shortest paths. If this is correct, then the correctnes proof should be rewritten a little so that it states all the cases. --[[User:Hdante|Hdante]] 18:40, 7 November 2005 (UTC)
| |||