Algoritmo de Ford-Bellman
El problema de los caminos más cortos desde un origen tiene solución solo si no hay un circuito sumidero alcanzable. El algoritmo de Ford-Bellman verifica que no haya un circuito hundido accesible desde s. Si es así, devuelve los caminos más cortos desde s. El algoritmo de Ford-Bellman es un algoritmo de programación dinámica codicioso que calcula los caminos más cortos de tamaño creciente. Es adecuado para cualquier grafico.
Condiciones.
- Caso general
Inicialmente, la distancia se inicializa a 0 para el origen y al infinito para los otros vértices.
Examinaremos todos los arcos y mejoraremos el valor de los caminos si es posible. El nuevo valor para cada vértice es la distancia mínima de todos los caminos de tamaño k-1 a los que sumamos las aristas que entran en el vértice. Como puede haber circuitos, hay que empezar de nuevo.
Por razones prácticas, resolver el algoritmo de Ford-Bellman solo devuelve un vector. Lo que corresponde a una columna actual de la tabla presentada.
Optimidad.
El camino más corto desde el origen a sí mismo es 0. Luego, los caminos de tamaño 1 se calculan de tal manera que solo mantenemos el camino más corto desde el origen hasta cualquier otro vértice.
el algoritmo calcula las rutas más cortas de las rutas de tamaño k (para la iteración k) a partir de las rutas más cortas de las rutas de tamaño k-1, por lo que es óptimo independientemente de la iteración de parada del algoritmo.
Si no existe tal circuito sumidero, un camino más corto es necesariamente elemental. Por lo tanto, estamos seguros de que se debe encontrar una ruta más corta en un máximo de n-1 pasos de la iteración. Si se mejora un valor de D es porque hay un circuito absorbente.
para cada vértice u del gráfico d [u, 0] = + ∞ d [s, 0] = 0
para k = 1 hasta Número de vértices - 1 hacer
para cada arco (u, v) del gráfico hacer
d [v, k]: = min (d [v, k-1], d [u, k-1] + peso (u, v))
fin
fin
volver d
Ejemplo
Tomemos el siguiente gráfico como ejemplo:
Tomemos el nodo 5 como fuente, luego inicializamos las otras distancias hasta el infinito. El vector π representa a los predecesores.
Iteración 1: Arcos (tu5,tu2) y (tu5,tu4) están relajados, actualizamos distancias y predecesores.
Iteración 2: Arcos (tu2,tu1), (tu4,tu2) y (tu4,tu3) están relajados, actualizamos las distancias a los nodos 1, 2 y 4. Tenga en cuenta que (tu4,tu2) encuentra una ruta más corta a 2 a través del nodo 4.
Iteración 3: Arcos (tu2,tu1) están relajados (porque encontramos una ruta más corta para ir al nodo 2 en la última iteración).
Iteración 4: Ningún arco está relajado.
Las rutas más cortas a partir del nodo 5 son:
El algoritmo se presenta en forma de tabla como se muestra a continuación:
| Iteración | 1 | 2 | 3 | 4 | 5 |
| 0 | inf | inf | inf | inf | 0 |
| 1 | inf | 4(5) | inf | 2(5) | 0 |
| 2 | 7(2) | 3(4) | 3(4) | 2(5) | 0 |
| 3 | 6(2) | 3(4) | 3(4) | 2(5) | 0 |
| 4 | 6(2) | 3(4) | 3(4) | 2(5) | 0 |
Las distancias en rojo muestran los nodos que han sufrido un cambio en la iteración actual. Por lo tanto, para la próxima iteración, los arcos que provienen de estos nodos deben relajarse. El algoritmo se detiene cuando no hay más cambios.
