
Utilisons l'algorithme de Dijkstra comme dans l'exercice pr\'ec\'edent.

\begin{center}
\begin{tabularx}{\linewidth}{|*9{>{\centering\arraybackslash}X|}}
\hline\rowcolor{purple}
\color{white}P & \color{white}A &\color{white} B &\color{white} C &\color{white} D &\color{white} E &\color{white} F &\color{white} G& \color{white}H\\
\hline
$\times$  & 
4 (P)  &  
\tikz[remember picture,overlay] 
\node (B) {6 (P)}; &  
\tikz[remember picture,overlay] 
\node (C) {11 (P)}; &  
12 (P)  &  & & &   \\
\hline
$\times$  & \cellcolor{violet!30} 4 (P)  & 7 (A)  &  11 (A) &   &   &  & &  \\
\hline
$\times$  & $\times$   &  
\cellcolor{violet!30} 
\tikz[remember picture,overlay] 
\node (B1) {6 (P)}; 
\tikz[remember picture,overlay] \draw[violet,thick,->,>=stealth'] (B.west) to[bend right=30] (B1.west);   &   & 10 (B)  &   &  && \\
\hline
$\times$  & $\times$   &  $\times$  &   & \cellcolor{violet!30} 10 (B)  &   & \tikz[remember picture,overlay] 
\node (F) {15 (D)}; & \tikz[remember picture,overlay] 
\node (G) {19 (D)}; &  \\
\hline
$\times$  & $\times$   & $\times$   &  \cellcolor{violet!30} 
\tikz[remember picture,overlay] 
\node (C1) {11 (P)}; 
\tikz[remember picture,overlay] \draw[violet,thick,->,>=stealth'] (C.west) to[bend right=30] (C1.west);  & $\times$  &  \tikz[remember picture,overlay] 
\node (E) {22 (C)};  &  & 21 (C) &  \\
\hline
$\times$  & $\times$   & $\times$   &  $\times$ & $\times$  &   & \cellcolor{violet!30} \tikz[remember picture,overlay] \node (F1) {15 (D)}; \tikz[remember picture,overlay] \draw[violet,thick,->,>=stealth'] (F.west) to[bend right=30] (F1.west);   & 23 (F) &   \\
\hline
$\times$  & $\times$   & $\times$   &  $\times$ & $\times$  &   & $\times$  & \cellcolor{violet!30} 
\tikz[remember picture,overlay] 
\node (G1) {19 (D)}; 
\tikz[remember picture,overlay] \draw[violet,thick,->,>=stealth'] (G.west) to[bend right=30] (G1.west);  &  \\
\hline
$\times$  & $\times$   & $\times$   &  $\times$ & $\times$  &   & $\times$  & $\times$  & 29 (G) \\
\hline
$\times$  & $\times$   & $\times$   &  $\times$ & $\times$  & \cellcolor{violet!30} \tikz[remember picture,overlay] 
\node (E1) {22 (C)}; 
\tikz[remember picture,overlay] \draw[violet,thick,->,>=stealth'] (E.west) to[bend right=30] (E1.west);  & $\times$  & $\times$  & 31 (E) \\
\hline
\end{tabularx}
\end{center}

\uline{La dur\'ee minimale est donc de 29 minutes avec le trajet $\rm P \to B \to D \to G \to H$.}