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

algoritmo de Ford-Bellman de ruta más corta

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.

algoritmo de Ford-Bellman de ruta más corta
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.

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 d

Ejemplo

Tomemos el siguiente gráfico como ejemplo:

algoritmo de Ford-Bellman de ruta más corta

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

algoritmo de Ford-Bellman de ruta más corta

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

algoritmo de Ford-Bellman de ruta más corta

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.

algoritmo de Ford-Bellman de ruta más corta

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

algoritmo de Ford-Bellman de ruta más corta

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

algoritmo de Ford-Bellman de ruta más corta

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

algoritmo de Ford-Bellman de ruta más corta

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.

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: