Algoritmo de Bellman-Ford

El algoritmo de Bellman-Ford determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. La diferencia de este algoritmo con los demás es que los pesos pueden tener valores

negativos ya que Bellman-Ford permite

detectar la existencia de un ciclo negativo.

EXPLICACIÓN DEL ALGORITMO

En el paso 0, inicializamos todas las distancias o costos mínimos a infinito. En el paso 1, actualizamos el paso anterior, aplicando las fórmulas.

En este caso ponemos la distancia de los nodos que tienen accesos directos al vértice 1, y se la sumamos a la distancia mínima acumulada que hay hasta el vértice oportuno.

Aquí esta distancia acumulada sería 0 para 1, debido que sería la distancia a él mismo, e infinito para el resto porque no han sido analizados todavía.

Matemáticas Discretas

Algoritmo de Bellman-Ford

En su estructura básica, es muy parecido al algoritmo de Dijkstra, pero en lugar de seleccionar vorazmente el nodo de peso mínimo aun sin procesar para relajarlo, simplemente relaja todas las aristas, y lo hace |V|-1 veces, siendo |V| el número de vértices en el grafo.

Las repeticiones permiten a las distancias mínimas recorrer el árbol, ya que en la ausencia de ciclos negativos, el camino más corto solo visita cada vértice una vez. A diferencia de la solución voraz, la cual depende de la suposición de que los pesos sean positivos, esta solución se aproxima más al caso general.

Segunda Iteración:

Luego de la segunda iteración obtendremos lo siguiente:

En este caso no actualizamos las distancias.

Hemos terminado la primera iteración, continuemos:

Ahora continuamos con vértice 5:

Realizamos paso de relajación para cada vértice adyacente:

Con vértice 2:  distancia[ 4 ] + 3 < distancia[ 2 ]    ->     2 + 3 < 7        ->       5 < 7

Con vértice 3:  distancia[ 4 ] + 8 < distancia[ 3 ]    ->     2 + 8 < 8       ->       10 < 8

Con vértice 5:  distancia[ 4 ] + 5 < distancia[ 5 ]    ->      2 + 5 < 13     ->       7 < 13

Actualizamos distancias para los vértices 2 y 5:

Ahora el siguiente vértice a evaluar es el vértice 4 que posee tres aristas:

Como el peso de su vértice adyacente es infinito actualizamos la distancia:

En este caso vemos que no se lleva acabo el paso de relajación:

distancia[ 2 ] + 2 < distancia[ 4 ]    ->        7 + 2 < 2         ->         9 < 2

Por lo tanto no actualizamos valores en la tabla. Ahora el siguiente vértice a evaluar es el vértice 3 que posee una sola arista:

Ahora continuamos con la arista que une al vértice 2 con el vértice 4:

Comenzamos por el vértice 3 y realizamos paso de relajación:

distancia[ 2 ] + 1 < distancia[ 3 ]    ->        7 + 1 < ∞         ->         8 < ∞

En esta oportunidad hemos encontrado una ruta más corta partiendo desde el vértice inicial al vértice 3, actualizamos la distancia en el vértice 3 y actualizamos el vértice previo al actual quedando:

Hemos terminado las aristas que parten del vértice 1, continuamos con las aristas que parten del vértice 2:

El paso de relajación es posible realizarlo entonces actualizamos la distancia en el vértice 4 quedando:

De manera similar al anterior vemos que la distancia actual desde el vértice inicial a 4 es ∞, verifiquemos el paso de relajación:

distancia[ 1 ] + 2 < distancia[ 4 ]    ->        0 + 2 < ∞         ->         2 < ∞

Ahora evaluamos al siguiente adyacente que es el vértice 4:

Ejemplo y código paso a paso

En esta iteración solamente se realizó el paso de relajación en la arista que une vértices 2 y 3. Para el grafo dado en la segunda iteración ya habremos obtenido la ruta más corta partiendo del vértice 1 a todos los demás vértices. Sin embargo no siempre obtendremos el óptimo en la 2da iteración, todo dependerá del grafo ingresado.

//Paso de relajación

void relajacion( int actual , int adyacente , int peso ){

    //Si la distancia del origen al vertice actual + peso de su arista es menor a la distancia del origen al vertice adyacente

    if( distancia[ actual ] + peso < distancia[ adyacente ] ){

        distancia[ adyacente ] = distancia[ actual ] + peso;  //relajamos el vertice actualizando la distancia

        previo[ adyacente ] = actual;                         //a su vez actualizamos el vertice previo

        Q.push( Node( adyacente , distancia[ adyacente ] ) ); //agregamos adyacente a la cola de prioridad

    }

}

Donde la función de relajación seria

1 for( int actual = 1 ; actual <= V ; ++actual ){  //Estos dos for = O(E)

 2 for( int j = 0 ; j < ady[ actual ].size() ; ++j ){ //reviso sus adyacentes del vertice actual

  3  int adyacente = ady[ actual ][ j ].v;    //id del vertice adyacente

  4   int peso = ady[ actual ][ j ].w;        //peso de la arista que une actual con adyacente ( actual , adyacente )

       //Realizamos paso de relajacion para la arista actual

   5  relajacion( actual , adyacente , peso );

   }

}

El paso de relajación se daría en la siguiente parte:

Vemos que la distancia actual desde el vértice inicial a 2 es ∞, verifiquemos el paso de relajación:

distancia[ 1 ] + 7 < distancia[ 2 ]    ->        0 + 7 < ∞         ->         7 < ∞

El paso de relajación es posible realizarlo entonces actualizamos la distancia en el vértice 2 quedando:

En el paso 2, al saber ya una distancia mínima acumulada desde los nodos 2 y 3 hasta 1, podemos actualizar las distancias mínimas de los nodos 4 y 5.

En los pasos sucesivos, se van actualizando las distancias mínimas acumuladas (D) de los distintos vértices hasta 1, y se van utilizando en los pasos siguientes para optimizar el camino mínimo. El final del algoritmo se da cuando no hay ningún cambio de un paso a otro, cuando ya no se puede encontrar un camino más corto

Evaluamos primero para vértice 2:

Las aristas de acuerdo al código serian de la forma e = (actual , adyacente , peso)donde actual es el vértice de donde partimos (en este caso sería 1) adyacente son los vértices que unen la arista e  (en este caso serían los vértices 2 y 4) y peso son los pesos de cada arista (en este caso tendríamos 7 y 2).

1 for( int actual = 1 ; actual <= V ; ++actual ){  //Estos dos for = O(E)

 2  for( int j = 0 ; j < ady[ actual ].size() ; ++j ){ //reviso sus adyacentes del vertice actual

 3      int adyacente = ady[ actual ][ j ].v;    //id del vertice adyacente

 4      int peso = ady[ actual ][ j ].w;        //peso de la arista que une actual con adyacente ( actual , adyacente )

5       …

6    }

7 }

Lo anterior en código

Como podemos observar tenemos 2 aristas, la que une vértice 1 con vértice 2 y vértice 1 con vértice 4

 Primera Iteración

Empezamos con las aristas que parten del vértice 1:

Ahora según Bellman-Ford debemos realizar el paso de relajación |V| – 1 = 5 – 1 = 4 veces para cada arista:

1 for( int i = 1 ; i <= V - 1 ; ++i ){ //Iteramos |V| - 1

veces

2 …

3 }

Inicialmente la distancia de vértice 1 -> vértice 1 es 0 por estar en el mismo lugar.

1 distancia[ inicial ] = 0;      //Este paso es importante, inicializamos la distancia del inicial como 0

Hasta el momento la tabla esta de la siguiente manera:

De acuerdo al vértice inicial que elijamos cambiara la distancia inicial, por ejemplo la ruta más corta partiendo del vértice 1 a todos los demás vértices.

1 //función de inicialización

2 void init(){

3  for( int i = 0 ; i <= V ; ++i ){

4    distancia[ i ] = INF;  //inicializamos todas las

distancias con valor infinito

5 previo[ i ] = -1;      //inicializamos el previo del  

vértice i con -1

6 }  

7 }

Y la función inicial será la siguiente:

1 vector< Node > ady[ MAX ]; //lista de adyacencia.

2 int distancia[ MAX ];      //distancia[ u ] distancia de vértice inicial a vértice con ID = u

3 int previo[ MAX ];         //para la impresión de caminos

4 int V;                     //numero de vértices

En cuanto al código los declaramos de la siguiente manera:

Inicializamos los valores de nuestros arreglos:

Dónde:

Vértices: ID de los vértices.

Distancia[ u ]: Distancia más corta desde vértice inicial a vértice con ID = u.

Previo[ u ]: Almacenara el ID del vértice anterior al vértice con ID = u, me servirá para impresión del camino más corto.

Tengamos el siguiente grafo, cuyos ID están en color negro encima de cada vértice, los pesos esta en color azul y la distancia inicial en cada vértice es infinito.

Este es el grafo final, con los caminos de costo mínimo de cada nodo.

Aplicaciones

Una variante distribuida del Algoritmo del Bellman-Ford se usa en protocolos de encaminamiento basados en vector de distancias, por ejemplo el Protocolo de encaminamiento de información (RIP). El algoritmo es distribuido porque envuelve una serie de nodos (routers) dentro de un Sistema autónomo(AS), un conjunto de redes y dispositivos router IP administrados típicamente por un Proveedor de Servicio de Internet (ISP). Se compone de los siguientes pasos:

*Cada nodo calcula la distancia entre él mismo y todos los demás dentro de un AS y almacena esta información en una tabla.

*Cada nodo envía su tabla a todos los nodos vecinos.

*Cuando un nodo recibe las tablas de distancias de sus vecinos, éste calcula la ruta más corta a los demás nodos y actualiza su tabla para reflejar los cambios.

Algoritmo en Pseudocódigo

Desventajas

Las desventajas principales del algoritmo de Bellman-Ford en este ajuste son:

*No escala bien

*Los cambios en la topología de red no se reflejan rápidamente ya que las actualizaciones se distribuyen nodo por nodo.

*Contando hasta el infinito(si un fallo de enlace o nodo hace que un nodo sea inalcanzable desde un conjunto de otros nodos, éstos pueden estar siempre aumentando gradualmente sus cálculos de distancia a él, y mientras tanto puede haber bucles de enrutamiento)

En esta otra tabla se muestran las soluciones parciales que se han ido obteniendo a través de la realización del algoritmo.

Considerar distancia[ i ] como la distancia más corta del vértice origen ingresado al vértice i y |V| el número de vértices del grafo.

1 método BellmanFord(Grafo,origen):

2 inicializamos las distancias con un valor grande

3 distancia[ origen ] = 0

4 para i = 1 hasta |V| - 1:

5 para cada arista E del Grafo:

6 sea ( u , v ) vértices que unen la arista E

7 sea w el peso entre vértices ( u , v )

8 Relajacion( u , v , w )

9 para cada arista E del Grafo:

10 sea ( u , v ) vértices que unen la arista E

11 sea w el peso entre vértices ( u , v )

12 si Relajacion( u , v , w )

13 Imprimir “Existe ciclo negativo”

15 Terminar Algoritmo

1 Relajacion( actual , adyacente , peso ):

2 si distancia[ actual ] + peso < distancia[ adyacente ]

3 distancia[ adyacente ] = distancia[ actual ] + peso

Descripción

En esta tabla están representados los nodos con los costos o distancias de sus respectivos nodos vecinos.

Como se ve en la tabla, los nodos que no son vecinos, se pone como costo el símbolo de infinito.

Análisis del Algoritmo

Mediante un ejemplo analizaremos el algoritmo:

Procedimiento para hallar el camino mínimo de todos los vértices a un único vértice destino.

Grafo inicial

Ciclos negativos

Para explicar los ciclos negativos, se tomará como

ejemplo el siguiente grafo:

Según Robert Sedgewick, “Los pesos negativos no son simplemente una curiosidad matemática; […] surgen de una forma natural en la reducción a problemas de caminos más cortos”

CONCLUSIONES

Concluimos que el Algoritmo de Bellman-Ford genera el camino mas corto en un grafo dirigido.

Se concluye que el Algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos.

Problema de Encontrar la Ruta más Corta

Se requiere llegar de la ciudad A a la ciudad B

Tenemos un mapa con distancias entre cada par de intersecciones.

¿Cómo encontramos la ruta más corta?

Enumerar todas las rutas de A a B, calcular la distancia y elegir la más corta.

Aún si quitamos ciclos, hay muchas posibilidades

Resolver el problema eficientemente.

Perla Alvarez

Luis Jasso

Daniel Méndez

Juan Reta

Cristian Rios

Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford