next up previous
suivant: Les algorithmes de plus monter: Plus courts chemins précédent: Notations

Le problème

Rechercher un plus court chemin de $ s$ vers $ t$ revient à rechercher un chemin de $ s$ vers $ t$ de longueur minimale s'il existe. Les conditions d'existence sont les suivantes :
  1. Il existe au moins un chemin de $ s$ vers $ t$
  2. Aucun chemin de $ s$ vers $ t$ ne contient de circuit absorbant i.e. de circuit de longueur négative.
En effet, si un tel circuit existait, l'on pourrait le parcourir indéfiniment pour abaisser la longueur du chemin. Dans la suite de cet exposé nous supposons :
  1. Il existe un chemin depuis un sommet $ s$ vers tous les autres sommets du graphe.
  2. Il n'existe pas de circuit absorbant dans le graphe.

\begin{theo}[Propriété de sous optimalité]
Soit $P^{s*}_t$\ un plus court che...
...*}_t$\ de $s$\ vers $k$\ est
un plus court chemin de $s$\ vers $k$.
\end{theo}
En effet, soit $ P$ un plus court chemin de $ s$ vers $ t$ passant par le sommet $ k$. Appelons $ P_1$ le sous chemin de $ s$ à $ k$ et $ P_3$ le sous chemin de $ k$ à $ t$. On a $ P = P_1 \Cup P_3$. Supposons que $ P_1$ ne soit pas optimal. Alors il existe un chemin $ P_2\,\neq\,P_1$ entre $ s$ et $ k$ tel que $ l(P_2) < l(P_1)$. Dans ce cas $ P_2 \Cup P_3$ est un chemin de $ s$ vers $ t$ de longueur inférieure à celle de $ P_1 \Cup P_3 = P$ ce qui contredit l'hypothèse.

Figure 3.1: Démonstration de la propriété de sous optimalité
\begin{figure}
\leavevmode
\begin{center}
\psfig{figure=sspccs.eps}
\end{center}
\end{figure}

Soit $ P^*$ un plus court chemin de la source $ s$ vers un sommet quelconque $ t$. Conséquence : Pour chaque arc $ (\ivj) \: \in \: P$, on a $ d(j)=d(i)+\cij$. La réciproque de cette propriété fondamentale fait l'objet du théorème suivant :
\begin{theo}
Soit un chemin $P=P_t^s$\ tel que
pour chaque arc $(\ivj)\:\in\...
...\,+\,c_{ij}$.
Alors $P$\ est un plus court chemin de $s$\ vers $t$.
\end{theo}
Dans cette démonstration, on utilise la notation $ P=\left(s=i_1,i_2,i_3,\ldots,i_{p-1},i_p=t\right)$. On part de $ d(t)$, plus courte distance de $ s$ à $ t$ que l'on décompose de manière à faire apparaître le coût des arcs composant $ P$ et le tour est joué.

\begin{displaymath}
\begin{array}{llllclcr}
d(t) &= &d(i_p) &= & & (d(i_p) &- ...
...& \\
& & & &+& (d(i_{2}) & - &d(i_{1})) \\
\end{array}
\end{displaymath}

avec $ d(i_1)=d(s)=0$ (hypothèse 2). Or, par hypothèse, pour tout arc $ (\ivj) \: \in \: P$, $ d(j)\:=\:d(i)\:+\:\cij$ ou, pour ce qui nous concerne ici : $ \cij\:=\:d(j)\:-\:d(i)$ Ce qui nous donne :

$\displaystyle d(t)\:=\:\sum\limits_{(\ivj) \in P} d(j)\:-d(i) \:=\: \sum\limits_{(\ivj) \in P} \cij \:=\:l(P)
$

La plus courte distance au sommet $ t$ étant égale à la longueur du chemin $ P$, celui-ci est un plus court chemin de $ s$ vers $ t$.
\begin{propriete}
Soit $G'=(X,\,E')$, où $E'$\ est l'ensemble des a...
...i)$. Alors, $G'$\ contient une arborescence enracinée en $s$.
\end{propriete}
Démonstration : Pour chaque sommet $ t$, il existe un plus court chemin de $ s$ à $ t$ dans $ G'$. Réciproquement, il suffit de construire une arborescence dans $ G'$ pour obtenir un plus court chemin depuis $ s$ vers tout autre sommet à l'aide d'un algorithme de parcours.
next up previous
suivant: Les algorithmes de plus monter: Plus courts chemins précédent: Notations
Bruno Garcia 2000-12-17