suivant: Le problème
monter: Plus courts chemins
précédent: Plus courts chemins
Ce chapitre suppose que l'on travaille sur un graphe orienté
, avec 
et 
. Chaque arc 
est muni d'un
coût 
.
Dans la suite on notera 
un chemin depuis un sommet 
(la
source) vers un sommet 
(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}](img106.png)
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}](img107.png)
![\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}](img108.png)
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}](img109.png)
![\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}](img110.png)
![\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}](img111.png)
En effet supposons qu'il existe deux sommets 
et 
tels que
. Ceci implique notament que l'arc 
n'est pas
utilisé dans le chemin 
associé à 
. Soit 
un plus court
chemin vers . Par définition sa longueur est 
. Si on lui ajoute
l'arc , on obtient un chemin de longueur
. D'où la
contradiction car est sensée être la plus courte distance pour
aller en .
Bruno Garcia
2000-12-17