\section{Dijkstra} {\large Algorithme de Dijkstra :} Plus courte chaîne du sommet $E$ au sommet $S$. \medskip \subsection{Dijkstra exemple 1} \medskip \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \GraphInit[vstyle=Dijkstra] \SetGraphUnit{4} \Vertices{square}{B,C,D,A} \SetGraphUnit{2.82} \NOWE(B){E} \NOEA(C){S} \Edge[label=$3$](E)(A) \Edge[label=$1$](E)(B) \Edge[label=$1$](A)(B) \Edge[label=$3$](B)(C) \Edge[label=$3$,style={pos=.25}](A)(C) \Edge[label=$5$,style={pos=.75}](B)(D) \Edge[label=$4$](A)(D) \Edge[label=$1$](S)(D) \Edge[label=$3$](C)(S) \Edge[label=$1$](C)(D) \end{tikzpicture} \end{tkzexample} \end{center} \def\ry{$\vrule width 5pt$} \def\iy{$\infty$} %<–––––––––––––––––——————————————————————————————————————————————————————————> \vbox{\tabskip=0pt \offinterlineskip \def\tablerule{\noalign{\hskip\tabskip\hrule}} \halign to \hsize{\strut#&\vrule # \tabskip=0.6em plus8em& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#\tabskip=0pt\cr\tablerule && $E$ && $A$ && $B$ && $C$ && $D$ && $S$ && Choix &\cr\tablerule && $0$ && \iy && \iy && \iy && \iy && \iy && $E$ &\cr\tablerule && \ry && $3(E)$ && $1(E)$ && \iy && \iy && \iy && $B$ &\cr\tablerule && \ry && $2(B)$ && \ry && $4(B)$ && $6(B)$ && \iy && $A$ &\cr\tablerule && \ry && \ry && \ry && $4(B)$ && $6(B)$ && \iy && $C$ &\cr\tablerule && \ry && \ry && \ry && \ry && $5(C)$ && $7(C)$ && $D$ &\cr\tablerule && \ry && \ry && \ry && \ry && \ry && $6(D)$ && $S$ &\cr\tablerule}} %<–––––––––––––––––——————————————————————————————————————————————————————————> \medskip Le plus court chemin est donc $EBCDS$ \vfill\newpage \subsection{Dijkstra exemple 2} \medskip \begin{center} \begin{tkzexample}[vbox] \begin{tikzpicture} \GraphInit[vstyle=Dijkstra] \SetGraphUnit{4} \Vertices{square}{G,D,A,F} \WE(F){H} \EA(A){B} \EA(D){C} \NO(A){E} \Edge[label=$1$](H)(F) \Edge[label=$4$](G)(F) \Edge[label=$2$](H)(G) \Edge[label=$2$](G)(D) \Edge[label=$3$](D)(C) \Edge[label=$4$](F)(E) \Edge[label=$3$](A)(D) \Edge[label=$2$](A)(E) \Edge[label=$1$](A)(B) \Edge[label=$2$](A)(C) \Edge[label=$2$](C)(B) \Edge[label=$3$](E)(B) \end{tikzpicture} \end{tkzexample} \end{center} %<–––––––––––––––––——————————————————————————————————————————————————————————> \vbox{\tabskip=0pt \offinterlineskip \def\tablerule{\noalign{\hskip\tabskip\hrule}} \halign to \hsize{\strut#&\vrule # \tabskip=0.6em plus8em& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#\tabskip=0pt\cr\tablerule && $H$ && $F$ && $G$ && $E$ && $D$ && $A$ && $C$ && $B$ && Choix &\cr\tablerule && $0$ && \iy && \iy && \iy && \iy && \iy && \iy && \iy && $H$ &\cr\tablerule && \ry && $1(H)$ && $2(H)$ && \iy && \iy && \iy && \iy && \iy && $F$ &\cr\tablerule && \ry && \ry && $2(H)$ && $5(F)$ && \iy && \iy && \iy && \iy && $G$ &\cr\tablerule && \ry && \ry && \ry && $5(F)$ && $4(G)$ && \iy && \iy && \iy && $D$ &\cr\tablerule && \ry && \ry && \ry && $5(F)$ && \ry && $7(D)$ && $7(D)$ && \iy && $E$ &\cr\tablerule && \ry && \ry && \ry && \ry && \ry && $7(D)$ && $7(D)$ && $8(E)$ && $A$ &\cr\tablerule && \ry && \ry && \ry && \ry && \ry && \ry && $7(D)$ && $8(E)$ && $C$ &\cr\tablerule && \ry && \ry && \ry && \ry && \ry && \ry && \ry && $8(E)$ && $B$ &\cr\tablerule}} %<–––––––––––––––––——————————————————————————————————————————————————————————> Le plus court chemin est donc $HFEB$ \begin{tkzexample}[code only] \def\ry{$\vrule width 5pt$} \def\iy{$\infty$} \vbox{\tabskip=0pt \offinterlineskip \def\tablerule{\noalign{\hskip\tabskip\hrule}} \halign to \hsize{\strut#&\vrule # \tabskip=0.6em plus8em& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#& \hfil#\hfil& \vrule#\tabskip=0pt\cr\tablerule && $H$ && $F$ && $G$ && $E$ && $D$ && $A$ && $C$ && $B$% && Choix &\cr\tablerule && $0$ && \iy && \iy && \iy && \iy && \iy && \iy && \iy% && $H$ &\cr\tablerule && \ry && $1(H)$ && $2(H)$ && \iy && \iy && \iy && \iy && \iy% && $F$ &\cr\tablerule && \ry && \ry && $2(H)$ && $5(F)$ && \iy && \iy && \iy && \iy% && $G$ &\cr\tablerule && \ry && \ry && \ry && $5(F)$ && $4(G)$ && \iy && \iy && \iy% && $D$ &\cr\tablerule && \ry && \ry && \ry && $5(F)$ && \ry && $7(D)$ && $7(D)$ && \iy% && $E$ &\cr\tablerule && \ry && \ry && \ry && \ry && \ry && $7(D)$ && $7(D)$ && $8(E)$% && $A$ &\cr\tablerule && \ry && \ry && \ry && \ry && \ry && \ry && $7(D)$ && $8(E)$% && $C$ &\cr\tablerule && \ry && \ry && \ry && \ry && \ry && \ry && \ry && $8(E)$% && $B$ &\cr\tablerule}} \end{tkzexample} \endinput