next up previous
suivant: Le problème monter: Plus courts chemins précédent: Plus courts chemins

Notations

Ce chapitre suppose que l'on travaille sur un graphe orienté $ G=(X,E)$, avec $ \vert X\vert=n$ et $ \vert E\vert=m$. Chaque arc $ (i,\,j)$ est muni d'un coût $ c_{ij}$. Dans la suite on notera $ P^s_t$ un chemin depuis un sommet $ s$ (la source) vers un sommet $ t$ (la destination).
\begin{defi}[Longueur d'un chemin]
On appelle \emph{longueur} d'un chemin $P$...
...equation}
l(P)=\sum\limits_{(i,\,j) \in P} c_{ij}
\end{equation}
\end{defi}
Remarque : on admettra qu'il existe toujours un chemin de longueur nulle d'un sommet vers lui mÍme.
\begin{defi}[Plus court chemin]
Un plus court chemin de $s$\ vers $t$\ est un...
...e $s$\ vers $t$. Dans la suite on
notera $P^{s*}_t$\ un tel chemin.
\end{defi}

\begin{defi}[Fonction de marquage, potentiel]
On appelle \emph{fonction de ma...
...ge} ou \emph{potentiel} une application de
$X$\ dans $\mathbb{R}$.
\end{defi}
En clair, cela revient à valuer, ou porter une valeur, sur chacun des sommets du graphe.
\begin{defi}[Plus courtes distances]
On appelle \emph{plus courte distance de...
...une fois la source $s$\ fix\'ee, on \'ecrira
$d(i)$\ pour $d_s(i)$.
\end{defi}

\begin{remarque}[Repr\'esentation d'un chemin]
Il existe deux grandes mani\\lq e...
..._2,\,i_3\: \ldots \:, i_{p-1},\,i_p=t \right)
\end{displaymath}
\end{remarque}

\begin{theo}[Condition d'optimalit\'e des distances]
Soit $d(.)$\ la plus cou...
...vj)\:\in\:G \qquad d(j)\:\leqslant\:d(i)\,+\,\cij
\end{displaymath}
\end{theo}
En effet supposons qu'il existe deux sommets $ i$ et $ j$ tels que $ d(j) > d(i)+\cij$. Ceci implique notament que l'arc $ (\ivj)$ n'est pas utilisé dans le chemin $ P_j$ associé à $ d(j)$. Soit $ P^*_i$ un plus court chemin vers $ i$. Par définition sa longueur est $ d(i)$. Si on lui ajoute l'arc $ (i,\,j)$, on obtient un chemin de longueur $ d(i)+\cij < d(j)$. D'où la contradiction car $ d(j)$ est sensée être la plus courte distance pour aller en $ j$.

Bruno Garcia 2000-12-17