Solution de Dijkstra
Définition
Soit \( \G\) un graphe. Une métrique ou une valuation sur \( \G\) est une application
\[\lambda : \Ar(\G)\longrightarrow ]0 ; +\infty[\]
On dira que le couple \( (\G,\lambda)\) est un graphe métrique ou graphe valué (orienté ou non orienté).
Dans la pratique on représente un graphe métrique en indiquant sur chaque arête la valeur de la métrique. Par exemple
\(
\xymatrix@R=1.79cm@C=2cm{
a\ar@{-}[r]^4\ar@{-}[d]_8\ar@{-}@/^2pc/[rr]_6&b\ar@{-}[r]^1\ar@{-}[d]^2\ar@{-}[dl]_2&c\ar@{-}[r]^4\ar@{-}[d]^6\ar@{-}[dl]_4&d\ar@{-}[d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}[dl]^3\\
e\ar@{-}[r]_1&f\ar@{-}[r]_2&g\ar@{-}[r]_1&h
}
\)
Étant donné un graphe métrique,
la solution de Dijkstra permet de déterminer la chaine la plus courte (au sens de la métrique) reliant un sommet fixé à tous les autres sommets du graphe.
§ Solution de Dijkstra (partant d'un sommet \( x\) ).
1. Initialisation
d_min(x)=0;
sommet_proche(x)={};
Pour tous les sommets y différent de x
d_min(y)=\( +\infty\) ;
sommet_proche(y)={};
Fin pour
2.
Tant qu'il existe des sommets non marqués
On marque un sommet y non marqué tel que d_min(y)
soit le plus petit possible.
Pour tout sommet z non marqué et successeur/voisin à y
Si d_min(z) > d_min(y)+\( \lambda\) ({y,z})
d_min(z) = d_min(y)+\( \lambda\) ({y,z});
sommet_proche(z) = y;
Fin si
Fin pour
Fin tant que
Faisons tourner cet algorithme sur le graphe métrique précédent. On présente les variables de l'algorithme dans un tableau que l'on complète au fur et à mesure.
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
\end{array}
\]
Initialisons les variables en convenant de laisser les cases vides lorsqu'elles valent \( +\infty\) :
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&0&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
\end{array}
\]
Les valeurs de chaque ligne représente le
d_min. L'algorithme nous indique qu'il faut choisir celui qui à le plus petit à chaque étape (
ie à chaque ligne). On encadre le sommet sélectionné, ici \( a\) , ce qui permet d'identifier son
sommet_proche. Le sommet ayant été sélectionné, on supprime (raye) les cases de la colonne \( a\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
\end{array}
\]
On complète la nouvelle ligne concernant le sommet sélectionné, c'est à dire \( a\) .
Ses sommets adjacents sont \( b\) , \( c\) et \( e\) .
- \( \bullet\)
- Puisque d_min(\( b\) ) > d_min(\( a\) )+\( \lambda(\{a,b\})\) (\( +\infty{>}0+4\) ) on modifie la colonne du sommet \( b\) .
- \( \bullet\)
- Puisque d_min(\( c\) ) > d_min(\( a\) )+\( \lambda(\{a,c\})\) (\( +\infty{>}0+6\) ) on modifie la colonne du sommet \( c\) .
- \( \bullet\)
- Puisque d_min(\( e\) ) > d_min(\( a\) )+\( \lambda(\{a,e\})\) (\( +\infty{>}0+8\) ) on modifie la colonne du sommet \( e\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&4&6&&8&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
\end{array}
\]
Le sommet au
d_min minimal non sélectionné est \( b\) . La nouvelle ligne sera donc \( b\) , on raye la valeur dans la colonne du sommet \( b\) et on remplis la nouvelle ligne. Ses sommets adjacents non sélectionnés sont \( c\) , \( e\) et \( f\) .
- \( \bullet\)
- Puisque d_min(\( f\) ) > d_min(\( b\) )+\( \lambda(\{b,f\})\) (\( +\infty{>}4+2\) ) on modifie la colonne du sommet \( f\) .
- \( \bullet\)
- Puisque d_min(\( e\) ) > d_min(\( b\) )+\( \lambda(\{b,e\})\) (\( 8{>}4+2\) ) on modifie la colonne du sommet \( e\) .
- \( \bullet\)
- Puisque d_min(\( c\) ) > d_min(\( b\) )+\( \lambda(\{b,c\})\) (\( 6{>}4+1\) ) on modifie la colonne du sommet \( c\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&\boxed{4}&6&&8&&&\\\hline
b&X&X&5&&6&6&&\\\hline
&X&X&&&&&&\\\hline
&X&X&&&&&&\\\hline
&X&X&&&&&&\\\hline
&X&X&&&&&&\\\hline
&X&X&&&&&&\\\hline
\end{array}
\]
Le sommet au
d_min minimal non sélectionné est \( c\) . Ses sommets adjacents non sélectionnés sont \( d\) , \( f\) et \( g\) .
- \( \bullet\)
- Puisque d_min(\( d\) ) > d_min(\( c\) )+\( \lambda(\{c,d\})\) (\( +\infty{>}5+4\) ) on modifie la colonne du sommet \( d\) .
- \( \bullet\)
- Puisque d_min(\( f\) ) \( \leqslant\) d_min(\( c\) )+\( \lambda(\{c,f\})\) (\( 6\leqslant5+4\) ) on ne modifie pas la colonne du sommet \( f\) .
- \( \bullet\)
- Puisque d_min(\( g\) ) > d_min(\( c\) )+\( \lambda(\{c,g\})\) (\( +\infty{>}5+6\) ) on modifie la colonne du sommet \( g\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&\boxed{4}&6&&8&&&\\\hline
b&X&X&\boxed{5}&&6&6&&\\\hline
c&X&X&X&9&6&6&11&\\\hline
&X&X&X&&&&&\\\hline
&X&X&X&&&&&\\\hline
&X&X&X&&&&&\\\hline
&X&X&X&&&&&\\\hline
\end{array}
\]
Le sommet au
d_min minimal non sélectionné est \( e\) (on aurait pu choisir \( f\) ; un tel choix ne change en rien le résultat final). Son sommet adjacent non sélectionné est \( f\) .
- \( \bullet\)
- Puisque d_min(\( f\) ) \( \leqslant\) d_min(\( e\) )+\( \lambda(\{e,f\})\) (\( 6\leqslant6+1\) ) on ne modifie pas la colonne du sommet \( f\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&\boxed{4}&6&&8&&&\\\hline
b&X&X&\boxed{5}&&\boxed{6}&6&&\\\hline
c&X&X&X&9&6&6&11&\\\hline
e&X&X&X&9&X&6&11&\\\hline
&X&X&X&&X&&&\\\hline
&X&X&X&&X&&&\\\hline
&X&X&X&&X&&&\\\hline
\end{array}
\]
Nous avons sélectionné le sommet \( e\) mais encadré son
d_min dans la ligne du sommet \( b\) . Il faut en effet choisir la première occurrence de son
d_min dans la colonne car l'encadrement permet aussi de garder en mémoire la valeur de
sommet_proche
Le sommet au
d_min minimal non sélectionné est \( f\) . Ses sommets adjacents non sélectionnés sont \( d\) et \( g\) .
- \( \bullet\)
- Puisque d_min(\( d\) ) > d_min(\( f\) )+\( \lambda(\{f,d\})\) (\( 9\leqslant 6+1\) ) on modifie la colonne du sommet \( d\) .
- \( \bullet\)
- Puisque d_min(\( g\) ) > d_min(\( f\) )+\( \lambda(\{f,g\})\) (\( 11\leqslant 6+2\) ) on modifie la colonne du sommet \( g\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&\boxed{4}&6&&8&&&\\\hline
b&X&X&\boxed{5}&&\boxed{6}&\boxed{6}&&\\\hline
c&X&X&X&9&6&6&11&\\\hline
e&X&X&X&9&X&6&11&\\\hline
f&X&X&X&7&X&X&8&\\\hline
&X&X&X&&X&X&&\\\hline
&X&X&X&&X&X&&\\\hline
\end{array}
\]
Le sommet au
d_min minimal non sélectionné est \( d\) . Ses sommets adjacents non marqués sont \( g\) et \( h\) .
- \( \bullet\)
- Puisque d_min(\( h\) ) > d_min(\( d\) )+\( \lambda(\{d,h\})\) (\( +\infty{>}7+3\) ) on modifie la colonne du sommet \( h\) .
- \( \bullet\)
- Puisque d_min(\( g\) ) \( \leqslant\) d_min(\( d\) )+\( \lambda(\{d,g\})\) (\( 8\leqslant7+3\) ) on ne modifie pas la colonne du sommet \( g\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&\boxed{4}&6&&8&&&\\\hline
b&X&X&\boxed{5}&&\boxed{6}&\boxed{6}&&\\\hline
c&X&X&X&9&6&6&11&\\\hline
e&X&X&X&9&X&6&11&\\\hline
f&X&X&X&\boxed{7}&X&X&8&\\\hline
d&X&X&X&X&X&X&8&10\\\hline
&X&X&X&X&X&X&&\\\hline
\end{array}
\]
Le sommet au
d_min minimal non sélectionné est \( g\) . On le marque. Son sommet adjacent non marqué est \( h\) .
- \( \bullet\)
- Puisque d_min(\( h\) ) > d_min(\( g\) )+\( \lambda(\{g,h\})\) (\( 10{>}8+1\) ) on modifie la colonne du sommet \( h\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&\boxed{4}&6&&8&&&\\\hline
b&X&X&\boxed{5}&&\boxed{6}&\boxed{6}&&\\\hline
c&X&X&X&9&6&6&11&\\\hline
e&X&X&X&9&X&6&11&\\\hline
f&X&X&X&\boxed{7}&X&X&\boxed{8}&\\\hline
d&X&X&X&X&X&X&8&10\\\hline
g&X&X&X&X&X&X&X&9\\\hline
\end{array}
\]
Le dernier sommet non marqué est \( h\) qui n'a pas de sommet adjacent.
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&\boxed{4}&6&&8&&&\\\hline
b&X&X&\boxed{5}&&\boxed{6}&\boxed{6}&&\\\hline
c&X&X&X&9&6&6&11&\\\hline
e&X&X&X&9&X&6&11&\\\hline
f&X&X&X&\boxed{7}&X&X&\boxed{8}&\\\hline
d&X&X&X&X&X&X&8&10\\\hline
g&X&X&X&X&X&X&X&\boxed{9}\\\hline
\end{array}
\]
Interprétation : le chemin le plus court au sens de la métrique du graphe entre \( a\) et \( h\) (par exemple) est de longueur \( 9\) . Il s'agit de la valeur encadrée dans la colonne \( h\) . Le sommet le plus proche pour arriver à \( h\) est le sommet \( g\) (ligne de la valeur encadrée dans la colonne du \( h\) ). Pur atteindre le sommet \( g\) , la distance minimal est de \( 8\) en passant par \( f\) , pour \( f\) il faut passer par \( b\) et \( b\) c'est par \( a\) . Ainsi le chemin le plus court entre \( a\) est \( h\) est \( abfgh\) .
De même pour les autres sommets. Les plus courtes chaines sont donc
\[a,\quad ab,\quad abc,\quad abfd,\quad abe,\quad abfg,\quad abfgh\]