Project Links Logo Artwork
Graph Theory: Networking
Home > Graph Theory: Networking > Shortest-Path Algorithms > Bellman-Ford Algorithm
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

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

  1. is the current estimate of the weight from vertex to vertex .
  2. 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;
 
 
go backgo forward
go backgo forward