Previous: Courts

Prototype


Next: Little
Plus long chemin dans un graphe
Le problème consiste à déterminer le poids du plus {\it long} chemin {\it acyclique} reliant un sommet à un autre du graphe.
Il n’est pas possible d’adapter directement les algorithmes de plus court chemin, compte tenu de l’existence possible de cycles dans le graphe.
Dans le cas général, on peut parcourir l’arbre des chemins acycliques partant d’un sommet s, au moyen d’un algorithme de parcours en profondeur utilisant une liste : 
parcourir le graphe :
POUR tout sommet t different de s
 d[s, t] = +inf
FINPOUR
d[s, s] = 0
visiter s

visiter un sommet t :
 ajouter t a la liste
 POUR tout successeur u de t qui n'est pas
 dans la liste
 SI d[s, u] = +inf
    ou d[s, u] < d[s, t] + p(t -> u)
 ALORS
  d[s, u] = d[s, t] + p(t -> u)
  FIN SI
  visiter u
 FIN POUR
 enlever t de la liste

Dans le cas particulier d’un graphe acyclique, on peut adapter efficacement les algorithmes de plus court chemin à la recherche des poids maximaux. La modification des algorithmes de Ford ou de Floyd consiste simplement à changer le sens de l’inégalité ; la modification de l’algorithme de Dijkstra est un peu plus compliquée (algorithme de Bellmann).
Algorithme de Bellmann
POUR tout sommet t
d[s, t] = +inf
FINPOUR
d[s, s] = 0
fixer s
TANT QU'il reste des sommets non fixes
 choisir un sommet t non fixe dont tous
 les predecesseurs sont fixe's
 POUR tout successeur u de t
  SI d[s, u] > d[s, t] + p(t -> u)
  ALORS
   d[s, u] = d[s, t] + p(t -> u)
  FIN SI
 FIN POUR
 fixer t
FIN TANT QUE

Exemple d’application de l’algorithme de Bellman Soit à chercher les plus longues distances depuis le sommet A dans le graphe suivant :

Rendered by QuickLaTeX.com


Le tableau suivant donne les plus longues distances depuis A calculées au cours des différentes étapes de l’algorithme :

\begin{tabular}{rccccc} sommets & {\sc a} & {\sc b} & {\sc c} & {\sc d} & {\sc e} \\ initialement & 0 & $\infty$ & $\infty$ & $\infty$ & $\infty$ \\ on fixe {\sc a} & & $\infty$ & 2 & 1 & $+\infty$ \\ on fixe {\sc c} & & 7 & & 6 & 5 \\ on fixe {\sc d} & & 7 & & & 5 \\ on fixe {\sc e} & & 8 & & & \\ valeurs finales & 0 & 8 & 2 & 6 & 5 \\ \end{tabular}
Previous: Courts
Next: Little