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