\documentclass[10pt] {article} \usepackage[T1]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,graphicx,multicol,mathrsfs, fancyhdr,enumerate,fourier,eurosym,alterqcm,enumerate,tabularx,variations,numprint}
\usepackage[dvips]{color}
\usepackage[tikz]{bclogo}
\usepackage{pst-plot,pst-tree,pstricks,pst-node,pstricks-add,pst-math,pst-xkey,pst-eucl}
\usepackage[francais]{babel} 
\everymath{\displaystyle}
%\usepackage[colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\textwidth 19cm \textheight 26cm \hoffset 
-1,4cm \voffset -3.7cm \oddsidemargin 0pt 
\renewcommand{\thesubsection}{\textcolor{blue}{\Roman{subsection}}} 
\renewcommand{\thesubsubsection}{\textcolor{blue}{\Roman{subsection}}.\textcolor{blue}{\arabic{subsubsection}}} 
\pagestyle{empty}
% pour le pied de page central
\cfoot{Page \thepage/\pageref{fin}}

\begin{document}
%\tableofcontents

\begin{center}\section*{\textcolor{red}{Correction des exercices}}\end{center}

\subsection{\textcolor{blue}{Pondichéry avril 2012}}
\begin{enumerate}
\item Le coefficient situé à la première ligne et dernière colonne de la matrice $M^4$ indique le nombre de chaînes de longueur 4 partant du sommet A et finissant au sommet H (les sommets étant notés dans l'ordre alphabétique dans la matrice $M$ associée au graphe).

     Ainsi, il y a 9 trajets possibles permettant d'aller du dép\^ot A au point de collecte H en quatre étapes.
\item On utilise l'algorithme de Dijkstra pour déterminer la chaîne la plus courte pour aller de A à H.

    $$\begin{array}{|*{9}{c|}}
    \hline
    A&B&C&D&E&F&G&H&\text{sommet sélectionné}\\ \hline
    0_A&\infty&\infty&\infty&\infty&\infty&\infty&\infty&A(0)\\ \hline
       &3_A&7_A&11_A&\infty&\infty&\infty&\infty&B(3)\\ \hline
       &   &6_B&10_B&14_B&\infty&\infty&\infty&C(6)\\ \hline
       &   &   &10_{(B;C)}&9_C&\infty&\infty&\infty&E(9)\\ \hline
       &   &   &10_{(B;C)}&   &17_E&19_E&\infty&D(10)\\ \hline
       &   &   &    &   &17_E&12_D&\infty&G(12)\\ \hline
       &   &   &    &   &16_G&    &24_G&F(16)\\ \hline
       &   &   &    &   &    &    &23_F&H(23)\\ \hline
    \end{array}$$
Il y a ainsi deux chemins qui minimisent le temps de trajet: il s'agit des chemins ABCDGFH et ABDGFH. 

Ces deux trajets durent 23 minutes, ce qui est donc le temps minimal de parcours.
\end{enumerate}

\subsection{\textcolor{blue}{Polynésie juin 2012}}

\begin{center}
\psset{unit=0.8cm}
\begin{pspicture}(0,0)(11,8.3)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\newcommand{\Pg}[1]{\small{\textsf{\prune{#1}}}}% poids des arêtes
\newcommand{\Sg}[1]{\small{\textsf{\bleu{#1}}}}% Sommet du graphe
\psset{dotstyle=*,dotscale=1.2,linecolor=bleu}
\dotnode(4,8){A} \dotnode(0,2.5){B} \dotnode(3.5,0){C} \dotnode(6,1.5){D} \dotnode(5.2,6){E} \dotnode(9,7.5){F} \dotnode(11,5.5){H} \dotnode(11,3){G} 
\uput[u](4,8){\Sg{A}} \uput[l](0,2.5){\Sg{B}} \uput[d](3.5,0){\Sg{C}} \uput[d](6,1.5){\Sg{D}} \uput[u](5.2,6){\Sg{E}} \uput[u](9,7.5){\Sg{F}} \uput[r](11,3){\Sg{G}} \uput[r](11,5.53){\Sg{H}}
\psset{linewidth=1pt,linecolor=bleu,shortput=nab}
\ncline{A}{B}_{\Pg{60}} \ncline{A}{C}^{\Pg{70}} \ncline{A}{E}^{\Pg{20}} \ncline{A}{F}^{\Pg{45}} \ncline{B}{C}_{\Pg{10}} \ncline{B}{E}_{\Pg{20}} \ncline{C}{D}_{\Pg{15}} 
\ncline{D}{E}_{\Pg{60}} \ncline{D}{G}_{\Pg{20}} \ncline{E}{F}^{\Pg{40}} \ncline{E}{H}_{\Pg{50}} \ncline{F}{H}^{\Pg{35}} \ncline{G}{H}_{\Pg{20}} 
\end{pspicture}
\end{center}
Pour déterminer le trajet le plus court, on utilise l'algorithme de Dijkstra :

\begin{center}
\begin{tabularx}{\linewidth}{|*{8}{>{\centering \arraybackslash}X|}m{1.15cm}|}\hline
A	&B		&C&D&E&F&G&H&Sommet retenu\\ \hline
0	&$\infty$&$\infty$&$\infty$	&$\infty$&$\infty$	&$\infty$	&$\infty$	&A(0)\\ \hline
	&60 (A)	&70 (A)	&$\infty$	&20 (A)	&45 (A) 	&$\infty$	&$\infty$	&E (20)\\ \hline
	&40 (E)	&70 (A)	&80 (E)		&		&45 (A)		&$\infty$	&70 (E)		&B (40)\\ \hline
	&		&50 (B)	&80 (E)		&		&45 (A)		&$\infty$	&70 (E)		&F (45)\\ \hline
	&		&50 (B)	&80 (E)		&		&			&$\infty$	&70 (E)		&C (50)\\ \hline
	&		&		&65 (C)		&		&			&$\infty$	&70 (E)		&D (65)\\ \hline
	&		&		&			&		&			&85 (D)		&70 (E)		&H (70)\\ \hline
	&		&		&			&		&			&85 (D)		&			&G (85)\\ \hline
\end{tabularx}
\end{center}
\bigskip

On retient le sommet G et ses prédécesseurs D C B E et A.

Le trajet le plus court est donc A -> E-> B-> C-> D-> G pour un temps de 85~min.
\label{fin}
\end{document}  