Bellman–Ford algorithm
Algoritmo de Bellman-Ford
- Date
- 1956-1959 · confidence high
- Place
- RAND Corporation, Santa Monica, California, United States
- Credited to
- Lester Ford Jr. and Richard Bellman (variant by Edward Moore)
- Field
- Knowledge & symbols
What was discovered
Ford published in 1956, at the RAND Corporation, a method to compute shortest paths from a source to all other vertices of a weighted directed graph, even with negative weights, through successive edge relaxations. Bellman formalized it in 1958.
Alfonso Shimbel had proposed a similar idea in 1955; Edward Moore published a variant in 1959, hence it is sometimes cited as "Bellman-Ford-Moore".
What it led to
- Detection of negative cycles in graphs
- Network routing via distance-vector protocols (RIP)
- Basis for network flow algorithms