El algoritmo de Bellman
El algoritmo de Bellman se basa en la siguiente observación: si conocemos todos los valores de los arcos (u, v) con u en un subgrafo y v fuera de este subgrafo. Si conocemos todos los caminos más cortos hacia u, entonces podemos calcular d(v) = min{d(u) + peso(u,v)}. El algoritmo de Bellmann es un algoritmo de programación dinámica codicioso (similar a una primera búsqueda de pan), visita todas las soluciones posibles.
Condiciones.
- Sin ciclo
- Solo arco
- Número finito de vértices
- Una fuente (y, de paso, un objetivo) definida
El algoritmo de Bellman toma como entrada a grafico orientada ponderada por números reales positivos y un vértice fuente. Se trata de construir progresivamente un subgrafo en el que se clasifican los diferentes vértices por orden creciente de su distancia mínima al vértice inicial. La distancia corresponde a la suma de los pesos de los arcos tomados.
Durante cada iteración, elegimos fuera del subgrafo un vértice tal que todos sus sucesores estén en el subgrafo y lo agregamos al subgrafo. Luego, actualizamos las distancias de los vértices vecinos del agregado. La actualización se realiza de la siguiente manera: la nueva distancia desde el vértice vecino es el mínimo entre la distancia existente y la obtenida sumando el peso del arco entre el vértice vecino y el vértice agregado a la distancia desde el vértice agregado.
Continuamos de esta manera hasta que se agoten las cumbres (o hasta que se seleccione la cumbre de llegada).
Por razones prácticas, resolver el algoritmo de Bellman solo devuelve un vector que contiene el vértice visitado, la lista de predecesores (los vértices ya validados) y los valores de las rutas más cortas a todos los demás vértices actualizados. Que corresponde a una fila actual de la tabla presentada.
Optimalidad
Un vértice se valida si se validan todos sus predecesores. Es decir, conocemos la camino más corto de todos sus antecesores. En el estado inicial, hemos validado el origen y conocemos los caminos de tamaño 1 a partir del origen. Por lo tanto, el siguiente vértice a validar tiene una ruta con solo vértices validados. Por inducción deducimos que hemos validado el camino más corto desde el origen hasta este vértice.
D [0] = 0;
para cada vértice i ‚0 hace C [i] = 0; D [i] = L [1, i];
para k = 1 año - 1 hacer
para cada yo sucesor de k hago
si (D [k] + L [k, i] <D [i]) luego D [i] = D [k] + L [k, i]; C [i] = k;
fin
fin
fin
Devolver a D
ES 
FR 
EN