Algoritmo de Ford-Bellman

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 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.

ruta más corta Algoritmo de Ford-Bellman ford

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.

ruta más corta Algoritmo de Ford-Bellman ford
algoritmo de Ford-Bellman de ruta más corta

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.

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 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 d

Ejemplo

Tomemos el siguiente gráfico como ejemplo:

ruta más corta Algoritmo de Ford-Bellman ford

Tomemos el nodo 5 como fuente, luego inicializamos las otras distancias hasta el infinito. El vector π representa a los predecesores.

ruta más corta Algoritmo de Ford-Bellman ford

Iteración 1: Arcos (tu5,tu2) y (tu5,tu4) están relajados, actualizamos distancias y predecesores.

ruta más corta Algoritmo de Ford-Bellman ford

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.

ruta más corta Algoritmo de Ford-Bellman ford

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).

ruta más corta Algoritmo de Ford-Bellman ford

Iteración 4: Ningún arco está relajado.

ruta más corta Algoritmo de Ford-Bellman ford

Las rutas más cortas a partir del nodo 5 son:

ruta más corta Algoritmo de Ford-Bellman ford

El algoritmo se presenta en forma de tabla como se muestra a continuación:

Iteración12345
0infinfinfinf0
1inf4(5)inf2(5)0
27(2)3(4)3(4)2(5)0
36(2)3(4)3(4)2(5)0
46(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.