Bellman-Ford Algorithm
The Bellman-Ford algorithm solves the
single-source shortest-path problem. It allows negative edge weights,
but does not allow a directed cycle of negative weight.
The Bellman-Ford algorithm returns false,
indicating that no solution exists, if it encounters a cycle of
negative weight that is reachable from the source. Otherwise, the
algorithm returns true, indicating that it has
found all shortest paths from the source.
The Algorithm
-
is the current estimate of the weight from vertex
to vertex .
-
is a predecessor of
.
In other words, the vertex through which the shortest distance from
to
was established.
for each vertex
for
for each edge
if
for each edge
if
return false;
return true;
|