Algoritmo De Bellman-Ford

ALGORITMO DE BELLMAN-FORD
Encuentra la mínima distancia de un nodo dado al resto de los nodos, y si se lleva información adicional, proporciona las tablas de encaminamiento, al igual que losanteriores.
Itera sobre el número de saltos, h, es decir, se busca el mejor camino, el de distancia más corta, con la restricción de llegar al destino en un número de saltos h (número de la iteración). Noencuentra las mejores rutas hasta que el algoritmo no se ha ejecutado por completo.
Es decir, consiste fundamentalmente en calcular la distancia de un nodo (aquel para el cual aplicamos elalgoritmo) a los demás sin dar ningún salto, luego dando uno, etc.
Sea el nodo i aquél para el que queremos encontrar las mejores rutas al resto de nodos. El algoritmo es el siguiente:
Pasos delalgoritmo:
1. PASO 0:

n = 0 ('n' es el número de saltos)

2. PASO 1:

Veamos el siguiente ejemplo con la red:

Tendremos entonces:

 
 
(Vemos que con un salto, 'cuesta' más llegaral nodo 3 (distancia 5) que con dos saltos (distancia 4))

y paramos, ya que (n=4) y (n=5) no aportan mejora alguna.
 
 Se prueba dando un salto más. Notar que está permitido el caso i=j,resultando entonces que no se da un nuevo salto (era mejor la ruta hallada antes).
Tiene una complejidad del orden de N3 por cada nodo que realiza el algoritmo, es decir, un orden mayor que Dijkstra. Elinterés del algoritmo radica en que se asemeja al de una red en la que se parte de la ignorancia total de un nodo, en la siguiente iteración conoce a sus nodos vecinos y así va progresivamenteconociendo nodos más lejanos. Puede verse que esta es la forma de trabajar de un encaminamiento mediante vector de distancias. Para ello, necesita ser enunciado de forma distribuida, de la forma que vemos acontinuación.

ALGORITMO DE BELLMAN-FORD DISTRIBUÍDO
Es la base de un algoritmo de vector de distancias. Se ejecuta para cada nodo i.

 
 
Pasos del algoritmo:
1. PASO 0:

2....