Bellman's algorithm

Bellman's algorithm

L’algorithme de Bellman est basé sur l’observation suivante: si nous connaissons toutes les valeurs des arcs (u, v) avec u dans un sous-graphe et v à l’extérieur de ce sous-graphe. Si nous connaissons tous les chemins les plus courts vers u, donc nous pouvons calculer d(v) = min{d(u) + poids(u,v)}. L’algorithme de Bellmann est un algorithm of dynamic programming greedy (similar to a first search for bread), he visits all the possible solutions.

Conditions.

  • No cycle
  • Arc only
  • Finite number of vertices
  • A source (and incidentally a target) defined

L’algorithme de Bellman prend en entrée un graph orienté pondéré par des réels positifs et un sommet source. Il s’agit de construire progressivement un sous-graphe dans lequel sont classés les différents sommets par ordre croissant de leur distance minimale au sommet de départ. La distance correspond à la somme des poids des arcs empruntés.

Initially, we consider that the distances from each vertex to the starting vertex are infinite except for the starting vertex for which the distance is 0. The starting subgraph is the empty set.

 During each iteration, we choose outside the subgraph a vertex such that all its successors are in the subgraph and we add it to the subgraph. Then, we update the distances of the neighboring vertices of the added one. The update takes place as follows: the new distance from the neighboring vertex is the minimum between the existing distance and that obtained by adding the weight of the arc between neighboring vertex and vertex added to the distance from the added vertex.

We continue in this way until the summits are exhausted (or until the arrival summit is selected).

shortest path bellman single source algorithm DAG
shortest path bellman single source algorithm DAG
shortest path bellman single source algorithm DAG

For practical reasons, solving the Bellman algorithm only returns a vector containing the visited vertex, the list of predecessors (the vertices already validated) and the values of the shortest paths to all the other updated vertices. Which corresponds to a current row of the presented table.

Optimality

Un sommet est validé si tous ses prédécesseurs sont validés. C’est-à-dire que l’on connaît le shortest way de tous ses prédécesseurs. À l’état initiale, nous avons validé l’origine et nous connaissons les chemins de taille 1 partant de l’origine. Le prochain sommet à valider possède donc un chemin avec uniquement des sommets validés. Par récurrence nous en déduisons que nous avons validé le plus court chemin de l’origine à ce sommet.

D [0] = 0;      
for each vertex i ‚0 make C [i] = 0; D [i] = L [1, i];   
for k = 1 year - 1 do  
    for each i successor of k do  
        if (D [k] + L [k, i] <D [i]) then D [i] = D [k] + L [k, i]; C [i] = k;            
        end      
    end     
end
To return to D
To share
en_GBEN
%d bloggers like this: