Algoritmo de Bellman-Ford

Algoritmo de Bellman-Ford

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.

¿Qué es?

Algoritmo de Bellman-Ford

Estructuras de datos y análisis de algoritmos

• Bernardo Andres Vega Borrero
• Luis Daniel Gómez Agredo

Profesor: Hector Niño Quiñonez

El algoritmo de Bellman-Ford genera el camino más corto desde un vértice origen en un grafo dirigido ponderado como lo hace el algoritmo de Dijkstra con la diferencia de que el Bellman-Ford puede hacerlo con pesos de aristas negativos. Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.

Algoritmo en pseudocódico

¿Cómo Trabaja?

Ciclos negativos

Cuando consideremos pesos negativos en las aristas, al momento de hallar la ruta más corta, es posible que se generen ciclos. Veamos el siguiente ejemplo:

El algoritmo parte de un vértice origen que será ingresado, a diferencia de Dijkstra que utiliza una técnica voraz para seleccionar vértices de menor peso y actualizar sus distancias mediante el paso de relajación, Bellman-Ford simplemente relaja todas las aristas y lo hace |V| – 1 veces, siendo |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

Ejemplo