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. L’algorithme de Ford-Bellman est un algoritmo de programación dinámica gourmand qui calcule les chemins les plus courts de taille croissante. Il convient à n’importe quel 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.

Le chemin le plus court de l’origine à lui-même est de 0. Puis les chemins de taille 1 sont calculés de telle sorte que nous ne gardons que le camino más corto de l’origine à tout autre sommet.

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.

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