
Nous allons voir pas \`a pas comment utiliser l'algorithme de Dijkstra.

\begin{itemize}
\item Avant tout, construisons une grille carrée \`a 7 lignes (plus une ligne en haut pour mettres les sommets dans un ordre qui suit \`a peu pr\`es celui du graphe pour mieux y voir) et 7 colonnes car il y a 7 sommets.
\begin{center}
\begin{tabular}{|*7{Sc|}}
\hline\rowcolor{purple}
\color{white}A &\color{white} B &\color{white} C &\color{white} D &\color{white} E &\color{white} F &\color{white} G\\
\hline
  &   &   &   &   &   &   \\
\hline
  &   &   &   &   &   &   \\
\hline
  &   &   &   &   &   &   \\
\hline
  &   &   &   &   &   &   \\
\hline
  &   &   &   &   &   &   \\
\hline
  &   &   &   &   &   &   \\
\hline
  &   &   &   &   &   &   \\
\hline
\end{tabular}
\end{center}

\item Nous partons du sommet A; par cons\'equent, nous allons mettre des croix dans la colonne sous \og A \fg. De A, nous pouvons aller jusqu'\`a B, C et E avec des distances respectives de 15, 13 et 11.
\begin{center}
\begin{tabular}{|*7{Sc|}}
\hline\rowcolor{purple}
\color{white}A &\color{white} B &\color{white} C &\color{white} D &\color{white} E &\color{white} F &\color{white} G\\
\hline
$\times$  & 15 (A)  &  13 (A) &   &  11 (A) &   &   \\
\hline
$\times$  &   &   &   &   &   &   \\
\hline
$\times$  &   &   &   &   &   &   \\
\hline
$\times$  &   &   &   &   &   &   \\
\hline
$\times$  &   &   &   &   &   &   \\
\hline
$\times$  &   &   &   &   &   &   \\
\hline
$\times$  &   &   &   &   &   &   \\
\hline
\end{tabular}
\end{center}
Nous mettons entre parenth\`eses le sommet duquel nous sommes arrivés (donc ici : A).

\item On prend le nombre le plus petit : 11 (A). On l'abaisse \`a la ligne suivante et on le marque (ici, j'ai colori\'e la cellule, mais on peut l'entourer), tout en mettant des croix dans la colonne correspondante :
\begin{center}
\begin{tabular}{|*7{Sc|}}
\hline\rowcolor{purple}
\color{white}A &\color{white} B &\color{white} C &\color{white} D &\color{white} E &\color{white} F &\color{white} G\\
\hline
$\times$  & 15 (A)  &  13 (A) &   &  11 (A) &   &   \\
\hline
$\times$  &   &   &   & \cellcolor{violet!30} 11 (A)  &   &   \\
\hline
$\times$  &   &   &   &  $\times$ &   &   \\
\hline
$\times$  &   &   &   &  $\times$ &   &   \\
\hline
$\times$  &   &   &   &  $\times$ &   &   \\
\hline
$\times$  &   &   &   &  $\times$ &   &   \\
\hline
$\times$  &   &   &   &  $\times$ &   &   \\
\hline
\end{tabular}
\end{center}

\item On part de E. Sur la m\^eme ligne, on met tous les sommets qui peuvent \^etre atteints : C (avec une distance totale de $11+9=20$), D (avec une distance totale de $11+8=19$), etc.
\begin{center}
\begin{tabular}{|*7{Sc|}}
\hline\rowcolor{purple}
\color{white}A &\color{white} B &\color{white} C &\color{white} D &\color{white} E &\color{white} F &\color{white} G\\
\hline
$\times$  & 15 (A)  &  13 (A) &   &  11 (A) &   &   \\
\hline
$\times$  & 26 (E)  & 20 (E)  & 19 (E)  & \cellcolor{violet!30} 11 (A)  & 30 (E)  & 41 (E)  \\
\hline
$\times$  &   &   &   &  $\times$ &   &   \\
\hline
$\times$  &   &   &   &  $\times$ &   &   \\
\hline
$\times$  &   &   &   &  $\times$ &   &   \\
\hline
$\times$  &   &   &   &  $\times$ &   &   \\
\hline
$\times$  &   &   &   &  $\times$ &   &   \\
\hline
\end{tabular}
\end{center}

\item Dans les colonnes o\`u il n'y a pas encore de croix, on regarde quel est le nombre le plus petit qui n'a pas encore \'et\'e marqu\'e : il s'agit ici de \og 13 (A) \fg{} : on l'abaisse donc \`a la ligne suivante, on met des croix dans la colonne et on le marque :
\begin{center}
\begin{tabular}{|*7{Sc|}}
\hline\rowcolor{purple}
\color{white}A &\color{white} B &\color{white} C &\color{white} D &\color{white} E &\color{white} F &\color{white} G\\
\hline
$\times$  & 15 (A)  &  \tikz[remember picture,overlay] \node (B) {13 (A)}; &   &  11 (A) &   &   \\
\hline
$\times$  & 26 (E)  & 20 (E)  & 19 (E)  & \cellcolor{violet!30} 11 (A)  & 30 (E)  & 41 (E)  \\
\hline
$\times$  &   & \cellcolor{violet!30} \tikz[remember picture,overlay] \node (B1) {13 (A)}; \tikz[remember picture,overlay] \draw[violet,thick,->,>=stealth'] (B.west) to[bend right=30] (B1.west);  &   &  $\times$ &   &   \\
\hline
$\times$  &   & $\times$   &   &  $\times$ &   &   \\
\hline
$\times$  &   & $\times$   &   &  $\times$ &   &   \\
\hline
$\times$  &   & $\times$   &   &  $\times$ &   &   \\
\hline
$\times$  &   & $\times$   &   &  $\times$ &   &   \\
\hline
\end{tabular}
\end{center}

\item En partant de C, on peut aller jusqu'\`a B, F, D et E (mais \og E \fg{} \'etant d\'eja marqu\'e, on l'oublie !). Donc sur cette m\^eme ligne o\`u l'on vient de marqu\'e le \og 13 (A) \fg, on  reporte dans les colonnes B, F et D les distances totales : $13+6=19$ pour B, $13+18=31$ pour F et $13+7=20$ pour F.
\begin{center}
\begin{tabular}{|*7{Sc|}}
\hline\rowcolor{purple}
\color{white}A &\color{white} B &\color{white} C &\color{white} D &\color{white} E &\color{white} F &\color{white} G\\
\hline
$\times$  & 15 (A)  &  13 (A) &   &  11 (A) &   &   \\
\hline
$\times$  & 26 (E)  & 20 (E)  & 19 (E)  & \cellcolor{violet!30} 11 (A)  & 30 (E)  & 41 (E)  \\
\hline
$\times$  &  19 (C) & \cellcolor{violet!30} 13 (A)  & 20 (C)  &  $\times$ & 31 (C)  &   \\
\hline
$\times$  &   & $\times$   &   &  $\times$ &   &   \\
\hline
$\times$  &   & $\times$   &   &  $\times$ &   &   \\
\hline
$\times$  &   & $\times$   &   &  $\times$ &   &   \\
\hline
$\times$  &   & $\times$   &   &  $\times$ &   &   \\
\hline
\end{tabular}
\end{center}

\item Dans les colonnes o\`u il n'y a pas de croix, parmi les nombres non marqu\'es, le plus petit est \og 15 (A) \fg. On l'abaisse donc \`a la ligne suivante, on le marque et on met des croix dans cette colonne.
\begin{center}
\begin{tabular}{|*7{Sc|}}
\hline\rowcolor{purple}
\color{white}A &\color{white} B &\color{white} C &\color{white} D &\color{white} E &\color{white} F &\color{white} G\\
\hline
$\times$  & \tikz[remember picture,overlay] \node (B) {15 (A)};  &  13 (A) &   &  11 (A) &   &   \\
\hline
$\times$  & 26 (E)  & 20 (E)  & 19 (E)  & \cellcolor{violet!30} 11 (A)  & 30 (E)  & 41 (E)  \\
\hline
$\times$  &  19 (C) & \cellcolor{violet!30} 13 (A)  & 20 (C)  &  $\times$ & 31 (C)  &   \\
\hline
$\times$  & \cellcolor{violet!30} \tikz[remember picture,overlay] \node (B1) {15 (A)}; \tikz[remember picture,overlay] \draw[violet,thick,->,>=stealth'] (B.west) to[bend right=30] (B1.west);  & $\times$   &  &  $\times$ &   &   \\
\hline
$\times$  & $\times$  & $\times$   &   &  $\times$ &   &   \\
\hline
$\times$  & $\times$  & $\times$   &   &  $\times$ &   &   \\
\hline
$\times$  & $\times$  & $\times$   &   &  $\times$ &   &   \\
\hline
\end{tabular}
\end{center}

\item En partant de B, on peut aller jusqu\`a F (le sommet C \'etant d\'ej\`a marqu\'e, on l'oublie !). On marque donc sur la m\^eme ligne et dans la colonne F la distance totale : $15+16=31$.
\begin{center}
\begin{tabular}{|*7{Sc|}}
\hline\rowcolor{purple}
\color{white}A &\color{white} B &\color{white} C &\color{white} D &\color{white} E &\color{white} F &\color{white} G\\
\hline
$\times$  & 15 (A)  &  13 (A) &   &  11 (A) &   &   \\
\hline
$\times$  & 26 (E)  & 20 (E)  & 19 (E)  & \cellcolor{violet!30} 11 (A)  & 30 (E)  & 41 (E)  \\
\hline
$\times$  &  19 (C) & \cellcolor{violet!30} 13 (A)  & 20 (C)  &  $\times$ & 31 (C)  &   \\
\hline
$\times$  & \cellcolor{violet!30} 15 (A) & $\times$   &  &  $\times$ & 31 (B)  &   \\
\hline
$\times$  & $\times$  & $\times$   &   &  $\times$ &   &   \\
\hline
$\times$  & $\times$  & $\times$   &   &  $\times$ &   &   \\
\hline
$\times$  & $\times$  & $\times$   &   &  $\times$ &   &   \\
\hline
\end{tabular}
\end{center}

\item Dans les colonnes non encore compl\'et\'ees d'une croix, on regarde quel est le nombre le plus petit : c'est ici \og 19 (E) \fg, que l'on s'empresse donc d'abaisser \`a la ligne suivante tout en compl\'etant la colonne de croix :
\begin{center}
\begin{tabular}{|*7{Sc|}}
\hline\rowcolor{purple}
\color{white}A &\color{white} B &\color{white} C &\color{white} D &\color{white} E &\color{white} F &\color{white} G\\
\hline
$\times$  & 15 (A)  &  13 (A) &   &  11 (A) &   &   \\
\hline
$\times$  & 26 (E)  & 20 (E)  & \tikz[remember picture,overlay] \node (B) {19 (E)};   & \cellcolor{violet!30} 11 (A)  & 30 (E)  & 41 (E)  \\
\hline
$\times$  &  19 (C) & \cellcolor{violet!30} 13 (A)  & 20 (C)  &  $\times$ & 31 (C)  &   \\
\hline
$\times$  & \cellcolor{violet!30} 15 (A) & $\times$   &  &  $\times$ & 31 (B)  &   \\
\hline
$\times$  & $\times$  & $\times$   &  \cellcolor{violet!30} \tikz[remember picture,overlay] \node (B1) {19 (E)}; \tikz[remember picture,overlay] \draw[violet,thick,->,>=stealth'] (B.west) to[bend right=30] (B1.west);  &  $\times$ &   &   \\
\hline
$\times$  & $\times$  & $\times$   &  $\times$  &  $\times$ &   &   \\
\hline
$\times$  & $\times$  & $\times$   &   $\times$ &  $\times$ &   &   \\
\hline
\end{tabular}
\end{center}

\item En partant de D, on peut aller jusqu\`a F (avec une distance totale de $19+2=21$) et G (avec une distance totale de $19+5=24$), que l'on met sur la m\^eme ligne :
\begin{center}
\begin{tabular}{|*7{Sc|}}
\hline\rowcolor{purple}
\color{white}A &\color{white} B &\color{white} C &\color{white} D &\color{white} E &\color{white} F &\color{white} G\\
\hline
$\times$  & 15 (A)  &  13 (A) &   &  11 (A) &   &   \\
\hline
$\times$  & 26 (E)  & 20 (E)  & 19 (E)   & \cellcolor{violet!30} 11 (A)  & 30 (E)  & 41 (E)  \\
\hline
$\times$  &  19 (C) & \cellcolor{violet!30} 13 (A)  & 20 (C)  &  $\times$ & 31 (C)  &   \\
\hline
$\times$  & \cellcolor{violet!30} 15 (A) & $\times$   &  &  $\times$ & 31 (B)  &   \\
\hline
$\times$  & $\times$  & $\times$   &  \cellcolor{violet!30} 19 (E) &  $\times$ & 21 (D)  & 24 (D)  \\
\hline
$\times$  & $\times$  & $\times$   &  $\times$  &  $\times$ &   &   \\
\hline
$\times$  & $\times$  & $\times$   &   $\times$ &  $\times$ &   &   \\
\hline
\end{tabular}
\end{center}

\item Dans les colonnes non encore compl\'et\'ees de croix, le plus petit nombre est \og 21 (D) \fg; on l'abaisse donc \`a la ligne suivante, on le marque et on compl\`ete la colonne d'une croix :
\begin{center}
\begin{tabular}{|*7{Sc|}}
\hline\rowcolor{purple}
\color{white}A &\color{white} B &\color{white} C &\color{white} D &\color{white} E &\color{white} F &\color{white} G\\
\hline
$\times$  & 15 (A)  &  13 (A) &   &  11 (A) &   &   \\
\hline
$\times$  & 26 (E)  & 20 (E)  & 19 (E)   & \cellcolor{violet!30} 11 (A)  & 30 (E)  & 41 (E)  \\
\hline
$\times$  &  19 (C) & \cellcolor{violet!30} 13 (A)  & 20 (C)  &  $\times$ & 31 (C)  &   \\
\hline
$\times$  & \cellcolor{violet!30} 15 (A) & $\times$   &  &  $\times$ & 31 (B)  &   \\
\hline
$\times$  & $\times$  & $\times$   &  \cellcolor{violet!30} 19 (E) &  $\times$ & 21 (D)  & 24 (D)  \\
\hline
$\times$  & $\times$  & $\times$   &  $\times$  &  $\times$ & \cellcolor{violet!30} 21 (D)  &   \\
\hline
$\times$  & $\times$  & $\times$   &   $\times$ &  $\times$ & $\times$  &   \\
\hline
\end{tabular}
\end{center}

\item Du sommet F, on peut aller jusqu'\`a G avec une distance totale de $21+1=22$. Comme 22 est le plus petit nombre de la colonne G, on le marque.
\begin{center}
\begin{tabular}{|*7{Sc|}}
\hline\rowcolor{purple}
\color{white}A &\color{white} B &\color{white} C &\color{white} D &\color{white} E &\color{white} F &\color{white} G\\
\hline
$\times$  & 15 (A)  &  13 (A) &   &  11 (A) &   &   \\
\hline
$\times$  & 26 (E)  & 20 (E)  & 19 (E)   & \cellcolor{violet!30} 11 (A)  & 30 (E)  & 41 (E)  \\
\hline
$\times$  &  19 (C) & \cellcolor{violet!30} 13 (A)  & 20 (C)  &  $\times$ & 31 (C)  &   \\
\hline
$\times$  & \cellcolor{violet!30} 15 (A) & $\times$   &  &  $\times$ & 31 (B)  &   \\
\hline
$\times$  & $\times$  & $\times$   &  \cellcolor{violet!30} 19 (E) &  $\times$ & 21 (D)  & 24 (D)  \\
\hline
$\times$  & $\times$  & $\times$   &  $\times$  &  $\times$ & \cellcolor{violet!30} 21 (D)  &   \\
\hline
$\times$  & $\times$  & $\times$   &   $\times$ &  $\times$ & $\times$  & \cellcolor{violet!30} 22 (F)  \\
\hline
\end{tabular}
\end{center}
\item \og 22 \fg{} est donc le poids minimal et la cha\^ine correspondante se trouve \`a l'aide des sommets entre parenth\`eses lus \`a l'envers en partant de G : 

G -- F -- D -- E -- A devient, \`a l'endroit :
\[
\rm A \to E \to D \to F \to G
\]
\end{itemize}
\newpage