Parcours des graphes

Prototype


Plus court chemin dans un graphe

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 \rightarrow j (+\infty si cet arc n’existe pas).
Une variante de l’algorithme de Warshall permet de calculer la matrice D telle que D_{[i, j]} soit le poids minimal d’un chemin de i à j :
D = M ;
POUR i  1 a n
 POUR j de 1 a n
  SI D[j, i] < +inf
  ALORS
   POUR k allant de 1 a 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. %{\bf Preuve de l’algorithme} : on montre par récurrence sur {\it i} qu’au %début du i^{i\grave eme} passage dans la boucle {\sc 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 \rightarrow b) le poids d’un arc a \rightarrow b.
Algorithme de Ford
POUR tout sommet t
d[s, t] = +inf
FINPOUR

d[s, s] = 0
REPETER
 POUR tout sommet t
 SI d[s, t] < +inf
 ALORS
  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
FIN SI
FIN POUR

TANT QU'on modifie quelque chose
%{\bf Preuve de l’algorithme} : on montre inductivement qu’au i^{i\grave eme} %passage dans la boucle {\sc repeter}, chacun des d[s, u] a pour valeur le %poids du plus court chemin de s à u comprenant moins de i sommets %intermédiaires. Il sénsuit que l’algorithme termine (on ne peut %passer plus de |S| - 1 fois dans la boucle {\sc repeter}) et qu’il %calcule bien les poids minimaux cherchés. % %Complexité : |S| \times |A|.
Algorithme de Dijkstra
POUR tout sommet t
d[s, t] = +inf
FINPOUR
d[s, s] = 0

TANT QU'il reste des sommets non fixe's
 choisir un sommet t non fixe'
 tel que d[s, t] soit minimale ;
 fixer t ;
 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
FIN TANT QUE
Exemple d’application de l’algorithme de Dijkstra. Soit à chercher les plus courts chemins depuis le sommet A dans le graphe suivant : \begin{figurette} \centerline{\includegraphics{Figures/chemins-courts.eps}} \end{figurette} Le tableau suivant donne les distances depuis A et les arcs marqués au cours des différentes étapes de l’algorithme :

Rendered by QuickLaTeX.com


 \begin{tabular}{rccccc}      sommets & {\sc a} & {\sc b} & {\sc c} & {\sc d} & {\sc e} \\ initialement & 0 & $\infty$  & $\infty$  & $\infty$  & $\infty$ \\ on fixe {\sc a} & & 8 ({\sc ab}) & 2 ({\sc ac}) & 1 ({\sc ad}) & $+\infty$ \\ on fixe {\sc d} & & 7 ({\sc db}) & 2            &              & $+\infty$ \\ on fixe {\sc c} & & 7            &              &          & 5 ({\sc ce}) \\ on fixe {\sc e} & & 6 ({\sc eb}) &              &          &              \\ valeurs finales & 0 & 6({\sc eb})& 2 ({\sc ac}) & 1 ({\sc ad}) & 5 ({\sc ce})\\ \end{tabular}
On obtient ainsi l’arborescence

Rendered by QuickLaTeX.com

Parcours des graphes