contenido
Algoritmo de Ford-Bellman
El problema de las trayectorias más cortas desde un origen solo puede resolverse si no hay un circuito absorbente alcanzable. El algoritmo de Ford-Bellman verifica que no haya ningún circuito de absorción accesible desde s. Si es así, devuelve los caminos más cortos desde s. El algoritmo Ford-Bellman es un codicioso algoritmo de programación dinámica que calcula las rutas más cortas de tamaño creciente. Es adecuado para cualquier gráfico.
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. Esto corresponde a una columna actual de la tabla presentada.
Optimidad.
La ruta más corta desde el origen hasta sí mismo es 0. Luego, las rutas de tamaño 1 se calculan de manera que solo mantengamos la ruta más corta 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 este circuito absorbente, un camino más corto es necesariamente elemental. Por lo tanto, estamos seguros de que se debe encontrar una ruta más corta en, como máximo, n-1 pasos de la iteración. Si se mejora un valor de D, significa que hay un circuito de absorción.
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 dEjemplo
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 siguiente iteración, los arcos que provienen de estos nodos deben relajarse. El algoritmo se detiene cuando no hay más cambios.
ES 
FR 
EN 
RU