| 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 Algorithmfor each vertex
					 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  for each edge  if      for each edge  if  return false;
				
				
				
				return true; |