Prototype |
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
, 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 :
Le tableau suivant donne les plus longues distances depuis
calculées au cours des différentes étapes de l’algorithme :
