Algorithme de Bellman

Contenus

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 algorithme de programmation dynamique gourmand (similaire à une première recherche de pain), il visite toutes les solutions possibles.

Conditions.

Pas de cycle
Arc uniquement
Nombre de sommets fini
Une source (et accessoirement une cible) définie

L’algorithme de Bellman prend en entrée un graphe 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.

Au départ, on considère que les distances de chaque sommet au sommet de départ sont infinies sauf pour le sommet de départ pour lequel la distance est de 0. Le sous-graphe de départ est l’ensemble vide.

Au cours de chaque itération, on choisit en dehors du sous-graphe un sommet tel que tous ses successeurs soient dans le sous-graphe et on l’ajoute au sous-graphe. Ensuite, on met à jour les distances des sommets voisins de celui ajouté. La mise à jour s’opère comme suit : la nouvelle distance du sommet voisin est le minimum entre la distance existante et celle obtenue en ajoutant le poids de l’arc entre sommet voisin et sommet ajouté à la distance du sommet ajouté.

On continue ainsi jusqu’à épuisement des sommets (ou jusqu’à sélection du sommet d’arrivée).

plus court chemin algorithme de bellman source unique DAG

Pour des raisons pratiques, la résolution du l’algorithme de Bellman ne retourne qu’un vecteur contenant le sommet visité, la liste des prédécesseurs (les sommets déjà validés) et les valeurs des plus courts chemins vers tous les autres sommets mise à jour. Ce qui correspond à une ligne courante du tableau présenté.

Optimalité

Un sommet est validé si tous ses prédécesseurs sont validés. C’est-à-dire que l’on connaît le plus court chemin 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;      
pour chaque sommet i ‚ 0 faire  
    C[i] = 0; D[i] = L[1, i];   
pour k = 1 a n - 1 faire  
    pour chaque i successeur de k faire  
        si (D[k] + L[k, i] < D[i]) alors         
            D[i] = D[k] + L[k, i];        
            C[i] = k;            
        fin      
    fin     
fin
Retourner D