Content deleted Content added
→A doubt: noticed I can't use refs in talk |
|||
Line 7:
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.
If both loops cycle directly through the number of vertexes (on the top loop) and on the edges (the second one), how come it would be "forever"? In such a loop there's no way it will be infinit. Or am I picturing the whole thing wrong?
== Zero weight cycles ==
| |||