Algoritmo de Bellman-Ford
Bellman–Ford algorithm
- Fecha
- 1956-1959 · fiabilidad alta
- Lugar
- RAND Corporation, Santa Mónica, California, Estados Unidos
- Autoría
- Lester Ford Jr. y Richard Bellman (variante de Edward Moore)
- Ámbito
- Saber y símbolos
Qué se descubrió
Ford publicó en 1956, en la RAND Corporation, un método para calcular los caminos más cortos desde un origen a todos los demás vértices de un grafo dirigido con pesos, incluso negativos, mediante relajaciones sucesivas de las aristas. Bellman lo formalizó en 1958.
Alfonso Shimbel había propuesto una idea similar en 1955; Edward Moore publicó una variante en 1959, de ahí que a veces se cite como «Bellman-Ford-Moore».
A qué dio paso
- Detección de ciclos negativos en grafos
- Enrutamiento en redes con el protocolo de vector de distancia (RIP)
- Base de algoritmos de flujo en redes