\documentclass[12pt] {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{colortbl}
\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 25cm \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{fancy}
% pour le pied de page central
\cfoot{Page \thepage/\pageref{fin}}
\title{\textcolor{red}{Graphes pondérés}}
\date{}
\begin{document}
%\tableofcontents

\maketitle


\subsection{\textcolor{blue}{Longueur d'une chaîne entre deux sommets}}

\begin{bclogo}[couleur = cyan!20, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définitions}}
\begin{enumerate}[$\bullet$]
\item \textbf{\textcolor{red}{Longueur d'une chaîne}} : nombre d'arêtes qui la composent.

\item \textbf{\textcolor{red}{Distance entre deux sommets :}} plus petite longueur des chaînes reliant ces deux sommets

\item \textbf{\textcolor{red}{diamètre d'un graphe :}} plus grande distance constante constatée entre deux sommets parmi toutes les paires de sommets

\item \textbf{\textcolor{red}{Poids d'une arête :}} Nombre positif qui lui est affecté (quelle que soit sa signification)

\item \textbf{\textcolor{red}{Poids d'une chaîne :}} somme des poids des arêtes qui la composent.

\item \textbf{\textcolor{red}{\og Plus courte chaîne\fg ou chaîne minimale entre deux sommets donnés :}} chaîne de poids minimal, parmi toutes celles qui relient ces deux sommets.
\end{enumerate}
\end{bclogo}

\textbf{\textcolor{red}{Remarque}} : ne pas confondre longueur d'une chaîne et son poids.\\\\


\subsection{\textcolor{blue}{Recherche d'une  chaîne de poids minimum : algorithme de Dijkstra}}
Lorsqu'un graphe pondéré comporte de nombreux sommets et de nombreuses arêtes, la recherche d'une plus courte chaîne peut être longue, car il convient d'examiner de nombreuses possibilités.\\
Le mathématicien Dijkstra a trouvé un algorithme commode pour trouver une plus court chaîne, ,sans oublier aucune possibilité, et cet algorithme peut être facilement programmé sur un ordinateur.


\textbf{\textcolor{red}{Présentation de cet algorithme sur un exemple :}}\\

Considérons le graphe :

\begin{center}
\begin{pspicture}(-1,-1)(4,3)
\psset{unit=2,arrowsize=2.5pt 3}
\cnodeput(0,2){A}{A}
\cnodeput(0,0){B}{B}
\cnodeput(2,2){C}{C}
\cnodeput(2,0){D}{D}
\cnodeput(3,1){E}{S}
\cnodeput(-1,1){F}{E}
\ncarc{-}{B}{A} \ncput*{1}
\ncarc{-}{B}{D} \ncput*{5}
\ncarc{-}{D}{C} \ncput*{1} 
\ncarc{-}{A}{C} \ncput*{3}
\ncarc{-}{A}{F} \ncput*{3}
\ncarc{-}{F}{B} \ncput*{1}
\ncarc{-}{C}{E} \ncput*{3}
\ncarc{-}{D}{E} \ncput*{1}
\ncarc{-}{B}{C} \ncput*{3}
\end{pspicture}
\end{center}
On va chercher une plus courte chaîne entre les sommets E et S.\\
\textbf{\textcolor{red}{Règles de construction :}}\\
Cet algorithme se construit de ligne en ligne en observant le graphe et en remplissant le tableau ci-contre au fur et à mesure.

\begin{tabular}{|l|l|} \hline
Étape&Tâches à effectuer\\
\hline
1&\begin{minipage}{16cm}

\begin{enumerate}[$\bullet$]
\item Placer tous les noms des sommets du graphe dans la première ligne du tableau

\item Sur la deuxième ligne du tableau, écrire le coefficient $0_A$ sous le sommet de départ A er $\infty$ sous les autres sommets.
\end{enumerate}
\end{minipage}
\\
\hline
2&\begin{minipage}{16cm}
\begin{enumerate}[$\bullet$]
\item Sur la dernière ligne écrite, repérer le sommet X de coefficient minimal

\item Commencer une nouvelle ligne et rayer toutes les cases vides sous X.
\end{enumerate}
\end{minipage}\\
\hline
3&\begin{minipage}{16cm}
\begin{enumerate}[$\bullet$]
\item Pour chaque sommet Y adjacent à X, calculer la somme P du coefficient de X et du poids de l'arête reliant X à Y.

\item Si P est strictement inférieur au coefficient actuel de Y, inscrire P(X) dans la case correspondante de la colonne Y.

\item Sinon, inscrire le coefficient de Y.

\item Compléter la ligne par les coefficients de la ligne précédente.
\end{enumerate}
\end{minipage}\\
\hline
4&\begin{minipage}{16cm}
\begin{enumerate}[$\bullet$]
\item S'il reste des sommets non sélectionnés, recommencer à l'étape 2.

\item Sinon, passer à l'étape 5.
\end{enumerate}
\end{minipage}\\
\hline
5&\begin{minipage}{16cm}
\begin{enumerate}[$\bullet$]
\item La longueur minimale est le nombre lu sur la dernière ligne du tableau.

\item Les sommets inscrits entre parenthèses permettent par remontée de trouver la chaîne minimale.
\end{enumerate}
\end{minipage}\\
\hline
\end{tabular}


\bigskip

\footnotesize{$\begin{array}{|*{8}{c|}}
\hline
\text{E}&\text{A}&\text{B}&\text{C}&\text{D}&\text{S}&\text{choix du sommet}&\text{coefficient}\\
\hline
0&\infty&\infty&\infty&\infty&\infty&\text{E}&0\\
\hline
\cellcolor{blue!20}&P=0+3=3~(\text{E})&p=0+1=1~(\text{E})&\infty&\infty&\infty&\text{B}&1\\
\hline
\cellcolor{blue!20}&P=1+1=2~(\text{B})&\cellcolor{blue!20}&P=1+3=4~(\text{B})&P=1+5=6~(\text{B})&\infty&\text{A}&2\\
\hline
\cellcolor{blue!20}&\cellcolor{blue!20}&\cellcolor{blue!20}&\begin{minipage}{2cm}P=2+3=5\textcolor{red}{>4}\\on garde 4~(\text{B})\end{minipage}&6~(\text{B})&\infty&C&4\\
\hline
\cellcolor{blue!20}&\cellcolor{blue!20}&\cellcolor{blue!20}&\cellcolor{blue!20}&p=4+1=5&P=4+3=7~(\text{C})&D&5\\
\hline
\cellcolor{blue!20}&\cellcolor{blue!20}&\cellcolor{blue!20}&\cellcolor{blue!20}&\cellcolor{blue!20}&P=5+1=6~(D)&S&6\\
\hline
\end{array}$}

On obtient comme chaîne : E-B-A-C-D-S, de poids 6


\bigskip

\textbf{\textcolor{red}{Autre exemple}} :\\
\parbox{8cm}{Des touristes sont logés dans un hôtel H.\\
Un guide souhaite leur faire visiter la région en empruntant les routes signalées comme d'intérêt touristique signalées par l'Office du tourisme.\\
Les tronçons de route qu'il souhaite emprunter sont représentées sur le graphe ci-contre.\\
Sur chaque arête figure la longueur en km des différents tronçons.\\
Un musée est situé en E.\\
Déterminer le plus court chemin menant de l'hôtel H au musée E.}\hfill
\parbox{12cm}{
\psset{xunit=1cm,yunit=0.7cm,algebraic=true,dimen=middle,dotstyle=o,dotsize=5pt 0,linewidth=1.6pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-4,-3)(5,4)
\cnodeput(-3,1){A}{B}
\cnodeput(0,3){B}{H}
\cnodeput(2,2){C}{D}
\cnodeput(4,-2){D}{F}
\cnodeput(2,-3){E}{E}
\cnodeput(0,-1){F}{C}
\cnodeput(-1.5,-2.42){G}{G}
\ncarc{-}{A}{B}\ncput*{12}
\ncarc{-}{B}{C}\ncput*{9}
\ncarc{-}{C}{D}\ncput*{21}
\ncarc{-}{D}{E}\ncput*{3}
\ncarc{-}{E}{G}\ncput*{9}
\ncarc{-}{G}{A}\ncput*{13}
\ncarc{-}{G}{F}\ncput*{7}
\ncarc{-}{F}{B}\ncput*{20}
\ncarc{-}{F}{C}\ncput*{8}
\ncarc{-}{F}{D}\ncput*{11}
\ncarc{-}{G}{D}\ncput*{5}
\end{pspicture*}}

\bigskip

$\begin{array}{|*{9}{c|}}\hline
H&B&D&F&E&G&C&\text{choix du sommet}&\text{coefficient}\\
\hline
0 (H)&\infty&\infty&\infty&\infty&\infty&\infty&H&0\\
\hline
X&12 (H)&9 (H)&\infty&\infty&\infty&20&D&9\\
\hline
X&12 (H)&X&30 (D)&\infty&\infty&17 (D)&B&12\\
\hline
X&X&X&30 (D)&\infty&25 (B)&17 (D)&C&17\\
\hline
X&X&X&28 (C)&\infty&24 (C)&X&G&24\\
\hline
X&X&X&28 (C)&33 (G)&X&X&F&28\\
\hline
X&X&X&X&31 (F)&X&X&E&31\\
\hline
\end{array}$

Le plus court chemin pour aller de H vers E mesure 31 km : c'est H-D-C-F-E.\\
On est effectivement arrivé à E en venant de F, à F en venant de C, à C en venant de D et à D en venant de H.
\label{fin}
\end{document}  