El algoritmo de Bellman

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.

Inicialmente, consideramos que las distancias desde cada vértice al vértice inicial son infinitas excepto para el vértice inicial para el cual la distancia es 0. El subgrafo inicial es el conjunto vacío.

 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).

camino más corto Bellman algoritmo de fuente única DAG
camino más corto Bellman algoritmo de fuente única DAG
camino más corto Bellman algoritmo de fuente única DAG

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
Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: