PROYECTO #5

Distancias: Algoritmo de Bellman-Ford.

Hola soy Carlos Triana de clase de los jueves y el tema que escogí fue Algoritmo de Bellman-Ford.

DEFINICIÓN DEL ALGORITMO:

El algoritmo de Bellman-Ford genera el camino más corto en un grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos. Por lo que el algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo. Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.

Si el grafo contiene un ciclo de coste negativo, el algoritmo lo detectará pero no encontrará el camino más corto que no repite ningún vértice, la complejidad de este problema es NP-completo.

EJEMPLO DEL ALGORITMO:

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

Grafo inicial





















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

















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

(Para que aprecien mejor la imagen hagan click sobre ella)

















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.

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.


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


















PSEUDOCÓDIGO:

Algoritmo de Bellman-Ford (camino mínimo)

Bellman-Ford (G,s)

Inicializar
for cada V perteneciente a V[G]
do d[v]=infinito
p[v]=nulo
p[s]=0

for i=1 to V[G]-1
do for cada arco (u,v) perteneciente a A[G]
Relajacion
if d[v] > d[u] + w(u,v) then
d[v] = d[u] + w(u,v)
p(v) = u

for cada arco (u,v) chequea lazo de peso
negativo
do if d[v] > d[u] + w (u,v) then
return FALSO el algoritmo no converge
return VERDADERO


Recomiendo este applet hecho en java sobre el algoritmo de Bellman-Ford, lo pueden encontrar en la siguiente liga:

http://neo.lcc.uma.es/evirtual/cdd/applets/BellmanFord/Example3.html



APLICACIONES:

El algoritmo de Bellman-Ford se usa en protocolos encaminamiento basados en vector de distancias, por ejemplo el Protocolo de encaminamiento de información (RIP).

También se usa en conjuntos de redes y dispositivos router pc administrados típicamente por un proveedor de servicios de internet (ISP) un ejemplo sería Telmex.


BIBLIOGRAFÍA:

http://es.wikipedia.org/wiki/Algoritmo_de_Bellman-Ford
http://es.wikipedia.org/wiki/Anexo:Ejemplo_de_Algoritmo_de_Bellman_-_Ford
http://neo.lcc.uma.es/evirtual/cdd/tutorial/red/bellman.html
http://neo.lcc.uma.es/evirtual/cdd/applets/BellmanFord/Example3.html
http://personales.upv.es/arodrigu/grafos/Ford.htm


LIGA A LAS DIAPOSITIVAS:

Bellman ford(jueves)

View more presentations from guest4ce8197.