<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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$}

%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”&gt;
\vbox{\tabskip=0pt \offinterlineskip
\def\tablerule{\noalign{\hskip\tabskip\hrule}}
\halign to \hsize{\strut#&amp;\vrule # \tabskip=0.6em plus8em&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#\tabskip=0pt\cr\tablerule
&amp;&amp; $E$ &amp;&amp;  $A$   &amp;&amp;  $B$   &amp;&amp;   $C$  &amp;&amp;  $D$   &amp;&amp; $S$    &amp;&amp; Choix    &amp;\cr\tablerule
&amp;&amp; $0$ &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; $E$       &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; $3(E)$ &amp;&amp; $1(E)$ &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; $B$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; $2(B)$ &amp;&amp; \ry    &amp;&amp; $4(B)$ &amp;&amp; $6(B)$ &amp;&amp; \iy    &amp;&amp; $A$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; $4(B)$ &amp;&amp; $6(B)$ &amp;&amp; \iy    &amp;&amp; $C$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; $5(C)$ &amp;&amp; $7(C)$ &amp;&amp; $D$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; $6(D)$ &amp;&amp; $S$    &amp;\cr\tablerule}}
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”&gt;

\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}
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”&gt;
\vbox{\tabskip=0pt \offinterlineskip
\def\tablerule{\noalign{\hskip\tabskip\hrule}}
\halign to \hsize{\strut#&amp;\vrule # \tabskip=0.6em plus8em&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#\tabskip=0pt\cr\tablerule
&amp;&amp; $H$ &amp;&amp;  $F$   &amp;&amp;  $G$   &amp;&amp;   $E$  &amp;&amp;  $D$   &amp;&amp; $A$    &amp;&amp; $C$    &amp;&amp; $B$    &amp;&amp; Choix   &amp;\cr\tablerule
&amp;&amp; $0$ &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; $H$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; $1(H)$ &amp;&amp; $2(H)$ &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; $F$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; $2(H)$ &amp;&amp; $5(F)$ &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; $G$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; $5(F)$ &amp;&amp; $4(G)$ &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; $D$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; $5(F)$ &amp;&amp; \ry    &amp;&amp; $7(D)$ &amp;&amp; $7(D)$ &amp;&amp; \iy    &amp;&amp; $E$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; $7(D)$ &amp;&amp; $7(D)$ &amp;&amp; $8(E)$ &amp;&amp; $A$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; $7(D)$ &amp;&amp; $8(E)$ &amp;&amp; $C$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; $8(E)$ &amp;&amp; $B$     &amp;\cr\tablerule}}
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”â€”&gt;

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#&amp;\vrule # \tabskip=0.6em plus8em&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#&amp;
\hfil#\hfil&amp; \vrule#\tabskip=0pt\cr\tablerule
&amp;&amp; $H$ &amp;&amp;  $F$   &amp;&amp;  $G$   &amp;&amp;   $E$  &amp;&amp;  $D$   &amp;&amp; $A$    &amp;&amp; $C$    &amp;&amp; $B$%
&amp;&amp; Choix   &amp;\cr\tablerule
&amp;&amp; $0$ &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy%
&amp;&amp; $H$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; $1(H)$ &amp;&amp; $2(H)$ &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy%
&amp;&amp; $F$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; $2(H)$ &amp;&amp; $5(F)$ &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy%
&amp;&amp; $G$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; $5(F)$ &amp;&amp; $4(G)$ &amp;&amp; \iy    &amp;&amp; \iy    &amp;&amp; \iy%
&amp;&amp; $D$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; $5(F)$ &amp;&amp; \ry    &amp;&amp; $7(D)$ &amp;&amp; $7(D)$ &amp;&amp; \iy%
&amp;&amp; $E$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; $7(D)$ &amp;&amp; $7(D)$ &amp;&amp; $8(E)$%
&amp;&amp; $A$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; $7(D)$ &amp;&amp; $8(E)$%
&amp;&amp; $C$     &amp;\cr\tablerule
&amp;&amp; \ry &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; \ry    &amp;&amp; $8(E)$%
&amp;&amp; $B$     &amp;\cr\tablerule}} 
\end{tkzexample}

\endinput</pre></body></html>