\documentstyle[a4,11pt,epsfig]{article}

\topmargin -1.5 cm
\oddsidemargin 0cm
\evensidemargin 0cm
\textwidth 16cm
\textheight 23cm
\parindent 0.5cm


\title{Devoir Surveill\'e d'Algorithmique - Maitrise d'Informatique}

\author{}
\date{21 Novembre 2001}

\begin{document}


\maketitle

\noindent
{\bf Dur\'ee:} 2 heures.

\noindent
{\bf Documents:} Seuls sont autoris\'es les notes manuscrites de cours et TD.

\noindent
{\bf NB:} Toutes les r\'eponses doivent \^etre clairement justifi\'ees.

\newcommand{\entier}{\mbox{$Z\!\!\!Z$}}

\section*{Exercice 1}

\bigskip
\noindent
{\bf Question 1:}
Comment utiliser l'algorihme de Floyd-Warshall pour d\'etecter la pr\'esence de
circuits de poids n\'egatifs dans un graphe pond\'er\'e $G$ ?

\bigskip
\noindent
{\bf Question 2:}
Modifier l'algorithme de Dijkstra pour qu'il puisse calculer le nombre
des chemins de poids minimal entre $s$ et chaque sommet du graphe.
Comment modifier l'algorithme pour qu'il produise
le chemin le plus court de poids minimal entre $s$ et les autres sommets.

\section*{Exercice 2}

L'algorithme de Floyd-Warshall vu en cours permet de calculer
les chemins de poids minimaux entre tous les couples de sommets
d'un graphe sans circuits de poids n\'egatifs.

Supposons que l'ensemble des sommets est $S = \{1,\ldots,n\}$.
On veut maintenant construire, pour chaque couple de sommets $(i,j)$,
un chemin de poids mininmum les reliant.
Pour cela, on cherche \`a d\'efinir une matrice $\Pi$
telle que, $\forall i,j \in \{1,\ldots,n\}$, $\Pi_{ij}$
est le pr\'ed\'ecesseur (p\`ere) de $j$ dans un chemin de poids minimal
allant de $i$ \`a $j$.
Noter que si $i = j$, on a $\Pi_{ij} = Nil$.

On adopte la m\^eme approche que celle utilis\'e dans l'algorithme de Floyd-Warshall.
On construit la matrice $\Pi$ en calculant it\'erativement une
s\'equence de matrices
$\Pi^0, \Pi^1, \ldots, \Pi^n$ avec $\Pi = \Pi^n$, o\`u,
$\Pi^k_{ij}$ est le pr\'ed\'ecesseur de $j$ dans un chemin de poids minimal
allant de $i$ \`a $j$ dont tous les sommets interm\'ediaires
sont dans $\{1,\ldots,k\}$.

\bigskip
\noindent
{\bf Question 1:}
Donner une d\'efinition r\'ecursive de $\Pi^k_{ij}$.

\bigskip
\noindent
{\bf Question 2:}
Int\'egrer le calcul de la matrice $\Pi$
dans le code de l'algorithme de Floyd-Warshall.


\section*{Exercice 3}

Soit $G = (S,A)$ un graphe orient\'e et
$p$ une fonction de pond\'eration $p \;\colon \; A \to \entier$,
o\`u $\entier$ est l'ensemble des entiers (positifs ou n\'egatifs).
On suppose que $G$ n'a pas de circuits, et pour simplifier,
qu'il a un unique sommet source $s$ (sommet n'ayant aucun arc incident).

\bigskip
\noindent
{\bf Question 1:}
Pourquoi l'algorithme de Dijkstra peut etre appliqu\'e \`a $G$ pour calculer
les chemins de poids minimum entre le sommet $s$ et tous les autres ?
\bigskip

On rappelle qu'un tri topologique des sommets d'un graphe
sans circuits est une s\'equence $s_1, \ldots, s_n$ ordonnant totalement l'ensemble $S$,
telle que, $\forall i,j \in \{1,\ldots,n\}$, si $(s_i,s_j) \in A$ alors $i < j$.

On consid\`ere une variante de l'algorithme de Dijkstra o\`u le choix des sommets
se fait selon un ordre topologique (au lieu d'utiliser l'op\'eration Extract-min).

\bigskip

\noindent
{\sc Dag-Poids-Min}$(G, p, s)$
\begin{itemize}
\item[] Trier topologiquement les sommets de $G$
\item[] Initialisation (comme dans Dijkstra)
\item[] {\bf Pour tout} sommet $u$ dans l'ordre du tri topologique {\bf faire}
\item[] \hspace{0.5cm}  {\bf Pour tout} sommet $v \in Adjacents(u)$
{\bf faire} $Relaxation(u,v)$
\end{itemize}

\bigskip

\noindent
{\bf Question 2:}
Montrer que cet algorithme est correct, c'est-\`a-dire, que lorsqu'il termine,
on a pour tout sommet $v \in S$, $d[v] = \delta(s,v)$.
(indication: Soit un chemin de poids min entre $s$ et $v$. Prouver
que pour tous les sommets $v_i$ de ce chemin, on a  $d[v_i] = \delta(s,v_i)$.
La preuve est par induction, et utilise un des lemmes vus en cours).

\bigskip

\noindent
{\bf Question 3:}
Evaluer la complexit\'e de cet algorithme.



\end{document}
