Content deleted Content added
occurance->occurrence(x2) |
m [[]] |
||
Line 1:
'''Bellman-Ford algorithm''' computes single-source shortest paths in a [[weighted graph]] (where some of the [[edge (graph theory)|edge]] weights may be negative). [[Dijkstra's algorithm]] accomplishes the same problem with a lower running time, but requires edges to be non-negative. Thus, Bellman-Ford is usually used only when there are negative edge weights.
Bellman Ford runs in O(VE) time, where V and E are the number of vertices and edges.
Line 18:
return false; //This means that the graph contains a cycle of negative weight and the shortest paths are not well defined
return true; //Lengths of shortest paths are in Distance array
== Proof of the Algorithm ==
| |||