Graphes et optimisation

Accueil > Cours > Algorithmes de plus court chemin

Algorithmes de plus court chemin

mercredi 29 mars 2006, par

On considère des graphes simples valués, c’est-à-dire dont chaque arc est muni d’un poids (nombre réel). Un chemin a pour poids la somme des poids des arcs qui le constituent.

Le problème des plus courts chemins consiste à déterminer le poids minimal d’un chemin d’un sommet à un autre, en supposant les poids positifs.

Algorithme de Floyd

On représente un graphe orienté valué à n sommets par une matrice carrée (n,n) de nombres : M[i,j] a pour valeur le poids de l’arc i->j(+ si cet arc n’existe pas).

Une variante de l’algorithme de Warshall permet de calculer la matriceDtelle que D[i,j] soit le poids minimal d’un chemin de i à j :

D:=M;
POUR i allant de 1 à n
        POUR j allant de 1 à n
                SI D[j,i]<ALORS
                        POUR k allant de 1 à n
                                SI D[j,k]>D[j,i]+D[i,k] ALORS
                                        D[j,k]:=D[j,i]+D[i,k]
                                FIN SI
                        FIN POUR
                FIN SI
        FIN POUR
FIN POUR

Cet algorithme résout le problème des plus courtes distances de tout sommet du graphe à tout autre sommet, mais ne donne pas le chemin correspondant.

Preuve de l’algorithme : on montre par récurrence sur i qu’au début du i-ième passage dans la boucle POUR extérieure, chacun des D[j,k] représente le poids minimal des chemins de j à k dont les sommets intermédiaires sont d’indice strictement inférieur à i.

Complexité : |S|3

Les algorithmes qui suivent permettent de déterminer les plus courts chemins d’un sommet particulier s du graphe à tout autre sommet. On notera p(a->b) le poids d’un arc a->b.

Algorithme de Ford


POUR tout sommet
        ;
FINPOUR;
;
RÉPÉTER
        POUR tout sommet
                SIALORS
                        POUR tout successeurde
                                SiALORS
                                       
                                FIN SI
                        FIN POUR
                FIN SI
        FIN POUR
TANT QU'on modifie quelque chose

Preuve de l’algorithme : on montre inductivement qu’au-ième passage dans la boucle RÉPÉTER, chacun desa pour valeur le poids du plus court chemin deàcomprenant moins desommets intermédiaires. Il s’ensuit que l’algorithme termine (on ne peut passer plus defois dans la boucle RÉPÉTER) et qu’il calcule bien les poids minimaux cherchés.

Complexité : (on examine au plus une fois chaque arc).
Une variante de l’algorithme de Ford permet de déterminer, pour chaque sommetaccessible depuis, un chemin de poids minimal deà : il suffit d’associer un arcà chaque sommetdistinct de, en mettant à jour les arcsen même temps que les distances :

...
                                SiALORS
                                       
                                       
                                FIN SI
...

Les arcs définissent une arborescence de racine, correspondant à des chemins de poids minimal d’origine.

Algorithme de Dijkstra

POUR tout sommet
       
FINPOUR;
;
TANT QU'il reste des sommets non fixés
        choisir un sommetnon fixé tel quesoit minimale;
        fixer;
        POUR tout successeur non fixéde
                SiALORS
                        ;
                        ;
                FIN SI
        FIN POUR
FIN TANT QUE

Preuve de l’algorithme : l’algorithme se termine, puisqu’à chaque passage dans la boucle TANT QUE on fixe un et un seul sommet.

On montre par récurrence qu’à toute étape de l’algorithme, pour tout sommet fixé,est le poids minimal d’un chemin deà. Supposons en effet cette propriété vérifiée avant que l’on ne fixe le sommet ; soitun chemin quelconque deà ; soitle plus grand entier tel quesoient des sommets fixés ; la façon dontest choisi implique que la distanceest inférieure ou égale à, donc, a fortiori, à la longueur du chemin ; par conséquenest bien le poids minimal d’un cheminde à.

Complexité : on passe exactementfois dans la boucle TANT QUE, et on examine 1 fois chacun des arcs (au moment où l’on fixe son origine). La détermination du sommet non fixé à distance minimale depeut se faire en temps constant, si l’on maintient une liste des sommets non fixés triée par ordre croissant de ; cette liste doit être remise à jour chaque fois que l’on change un, ce qui peut se faire enopérations. La complexité est ainsi : cet algorithme est donc plus efficace que l’algorithme de Ford.

Exemple d’application de l’algorithme de Dijkstra
Soit à chercher les plus courts chemins depuis le sommetdans le graphe suivant :

Le tableau suivant donne les distances depuis et les arcs marqués au cours des différentes étapes de l’algorithme :

sommets
A
B
C
D
E
initialement
0

on fixe A

8 (AB)
2 (AC)
1 (AD)

on fixe D

7 (DB)
2

on fixe C

7

5 (CE)
on fixe E

6 (EB)

valeurs finales
0
6 (EB)
2 (AC)
1 (AD)
5 (CE)
On obtient ainsi l’arborescence

Algorithme de Bellmann

Dans le cas particulier d’un graphe sans circuit, l’algorithme de Bellmann permet de déterminer rapidement les plus courts chemins depuis un sommet :

Restreindre le graphe aux sommets accessibles depuis;
POUR tout sommet
       
FINPOUR
;
TANT QU'il reste des sommets non fixés
        fixer un sommet non fixédont tous les prédécesseurs sont fixés;
        POUR tout successeurde
                SiALOR
                       
                FIN SI
        FIN POUR;
FIN TANT QUE

Preuve de l’algorithme : on montre inductivement que les distances des sommets fixés sont bien les poids des plus courts chemins depuis(un chemin de poids minimal deàétant minimal parmi les chemins minimaux deà un prédécesseur desuivis de l’arc liant ce prédécesseur à).

Complexité : restreindre le graphe aux sommets accessibles depuisse fait en temps de l’ordre de ; on passe au plus fois dans la boucle TANT QUE (en fixant un sommet) et on examine une fois chaque arc (lorsqu’on fixe son origine). Le choix du sommet à fixer peut se faire en temps constant, si l’on met à jour une liste appropriée sans augmenter la complexité globale (on peut par exemple initialiser pour chaque sommet un compteur au nombre de ses prédécesseurs ; chaque fois qu’on fixe un sommet, on décrémente le compteur de ses successeurs ; si ce compteur passe à zéro, on insère le sommet correspondant dans la liste des sommets que l’on peut fixer).

En définitive, la complexité est de l’ordre de.