Admin CliCours
Memoriser les chemins
En plus de calculer la longueur d’un plus court chemin depuis s, on peut aussi stocker un plus court chemin. En effet, a` chaque fois qu’on relˆache un arc (u, v), cela signifie que le chemin de s a` v passe dor´enavant par u, autrement dit le pr´ed´ecesseur de v est maintenant le sommet u. On peut par exemple stocker ces pr´ed´ecesseurs dans un tableaux index´ par les sommets du graphe. Voir l’algorithme 2 ci-contre pour une impl´ementation (les lignes correspondantes sont en bleu).
Detecter si un graphe quelconque a un circuit negatif
On peut montrer que l’algorithme de Bellman-Ford (Algorithme 1) s’arrˆete apr`es au plus n −1 executions de la boucle Tant que, dans le cas d’un graphe sans circuit de poids n´egatif (ici n est le nombres de sommets du graphe). La preuve se fait par r´ecurrence sur le nombre d’it´erations et l’hypoth`ese de r´ecurrence est la suivante. Au bout de x it´erations de la boucle Tant Que, pour tout sommet v, L[v] est la longueur du plus court chemin de s a` v parmi ceux qui ont au plus x arcs.
Si un graphe connexe a un circuit n´egatif, alors il n’y a pas de plus court chemin depuis s vers certains sommets (en particuliers ceux qui sont sur ce circuit n´egatif). Donc, l’algorithme 1 sur un tel graphe executerait ind´efini-ment dans la boucle Tant Que. En particulier, cette derni`ere s’executerait au moins n fois. On peut donc executer la boucle Tant Que n fois sur un graphe quelconque, et si a` la derni`ere it´eration, la valeur de L change, alors on sait qu’il y a un circuit négatif.
Voir l’algorithme 2 ci-contre pour une impl´ementation (les lignes corres-pondantes sont en vert).
Variantes
Le cas dual : distance vers un sommet Au lieu de calculer des plus courts chemins depuis s vers tous les sommets, on peut calculer la distance des plus courts chemins depuis n’importe quel sommet a` un sommet t (voir algorithme 3).
Algorithme 3 : Variante de Bellman-Ford (le cas dual)
Donn´ees−→
G un graphe orient´ valu´e sans circuit de longueur strictement n´egative −→
t un sommet de G
Variables locales
L tableau des distances vers un sommet a` t
Succ tableau des successeurs sur un plus court chemin a` t (u, v) un arc
d´ebut
initialisation
L[t] := 0
pour tous les sommet v 6= t faire L[v] := +∞ tant que L change faire
→−
pour chaque arc (u, v) de G faire
−→
si L(u)>L(v)+length((u, v, G )) alors →−
L(u) :=L(v)+length((u, v, G))
Succ[u] :=v
finsi
finprch
fintq
fin
Sorties : L, succ
Plus long chemin vers un sommet Au lieu de calculer des plus courts chemins depuis s vers tous les sommets, on peut calculer la distance des plus longs chemins. Bien evidemment, l’algorithme a maintenant des limitations diff´erentes : il n’a de sens que dans un graphe sans circuit strictement positif (voir algorithme 4).
Algorithme 4 : Autre variante de Bellman-Ford (plus long chemin)
Donn´ees
−→
G un graphe orient´ valu´e sans circuit de longueur strictement positive →−
s un sommet de G
Variables locales
L tableau des distances depuis un sommet s
P red tableau des successeurs sur un plus court chemin a` t (u, v) un arc
d´ebut
initialisation
L[s] := 0
pour tous les sommet v 6= s faire L[v] := −∞ tant que L change faire
−→
pour chaque arc (u, v) de G faire
→−
si L(v)<L(u)+length((u, v, G )) alors −→
L(v) :=L(u)+length((u, v, G))
Pred[v] :=u
finsi
finprch
fintq
fin
Sorties : L, Pred
Télécharger le cours complet
