Vidéo (11 min): Les idées clefs de Bellman-Ford

 
Cette vidéo suppose que vous avez déjà fait un effort de lecture du polycopié et notamment des notions de graphes orientés, plus courts chemins, circuits absorbants et que vous avez essayé d'appliquer l'algorithme par vous même.

On essaye de reprendre les propriétés et observations qui sont sous-jacentes à cet algorithme.


La formule de récurrence donnée dans la vidéo est \phi(i,v) = \min_{u \in \Gamma^-(v)}(\phi(i-1,u) + w(u,v)). Ce cas général suppose que tout sommet à au moins un prédécesseur (sinon il n'y a aucun sommet u sur lequel effectuer le min et la valeur n'est pas définie). C'est un cas extrême mais, en toute rigueur, il faudrait le prendre en compte et écrire simplement:

\phi(i,v) = \min(+\infty, \min_{u \in \Gamma^-(v)}(\phi(i-1,u) + w(u,v))

Notations (rappels)

  • G=(V,A) un graphe orienté de n sommets et m arcs avec une pondération w(i,j) pour chaque arc (i,j) \in A.

  • \delta(u,v) : la distance d'un plus court chemin de u à v (on prendra \delta(u,v) = +\infty par convention si il n'existe pas de chemin de u à v).

  • Un plus court chemin (pcc) de u à v est n'importe quel chemin p =\: <u, \ldots, v> du sommet u au sommet v de distance w(p) = \delta(u,v). Il peut en effet y avoir plusieurs chemins optimaux.

 

Optimalité de Bellman-Ford

Proposition: Si G ne contient pas de circuits absorbants alors à la fin de l'exécution de l'algorithme on a d[n-1,v] = \delta(s,v) pour tout sommet v atteignable depuis s.

Preuve: Montrons par récurrence qu'à l'itération i, \phi[i,v] contient la valeur du plus court chemin de s à v d'au plus i arcs que l'on notera également \delta^{i}(s,v). C'est vrai pour i=0 puisque \phi[0,s] = 0 et \phi[0,v] = +\infty pour tous les autres sommets v \neq s après la phase d'initialisation. Supposons la propriété vraie à l'itération i-1 pour un v quelconque, on sait d'après l'observation 1 "Les sous-chemins d'un plus court chemin sont des plus courts chemins" que:

\delta^{i}(s,v) = min(\delta^{i-1}(s,v), min_{(u,v) \in A} (\delta^{i-1}(s,u) + w(u,v))) 

Or à l'itération i, tous les arcs de E sont mis à jour (ligne 4-6) et en particulier pour v, tous les arcs (u,v) atteignant v depuis u. Ainsi à la fin de l'itération i, d[i,v] contient la valeur du plus court chemin d'au plus i arcs. Enfin tout plus court chemin à au plus |V|-1 arcs (voir l'observation 2 énonçant "qu'un plus court chemin ne contient pas de circuit") donc \phi[n-1,v] = \delta(s,v) au bout de |V|-1 itérations (ligne 3) ce qui termine la preuve.

Notons à propos de l'observation 2 qu'un plus court chemin pourrait contenir un circuit de distance nulle mais on a un chemin de même distance en évitant de parcourir ce circuit donc il existe toujours une solution optimale sans circuit.

Contact: Nicolas Catusse et Hadrien Cambazard

Last modified: Tuesday, 24 September 2019, 5:29 PM