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.

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é

Soit $P^*$ un plus court chemin de la source $s$ vers un sommet quelconque $t$.

• Par définition de la plus courte distance (3.4), $d(t) = l(P^*)$.
• Par application de la propriété précédente, $d(i) = l(P^{s*}_i)$ pour chacun des sommets $i \: \in P^*$, où $P^{s*}_i$ est la restruction de $P^*$ entre $s$ et $i$.

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 :

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{array}{llllclcr} d(t) &= &d(i_p) &= & & (d(i_p) &- ... ...& \\ & & & &+& (d(i_{2}) & - &d(i_{1})) \\ \end{array}$$

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 :

$$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$.

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.