Arcs à coûts positifs, algorithme de Dijkstra

Lorsque le réseau contient des circuits, il n'est plus possible d'utiliser l'algorithme précédent qui s'appuie sur un tri topologique. Toutefois, il est toujours possible de tirer profit de la non négativité des coûts sur les arcs. Pour ce faire on partitionne l'ensemble des sommets en deux ensembles $S$ et $\overline{S}$. Les sommets de $S$ sont dits fixés et ceux de $\overline{S}$ temporaires. On utilise une fonction de marquage $d(.)$ que nous appellerons distance et qui à la fin de l'algorithme sera égale à la distance minimale depuis $s$ vers chaque sommet. A chaque étape, la définition de $d$ est la suivante :

$d(i)$ est la longueur d'un plus court chemin de $s$ vers $i$ dont tous les sommets intermédiaires sont dans $S$. Initialement, $d(s)=0$ et $d(i)=+\infty$, $\forall \; i\,\neq\,s$.

L'algorithme repose sur le postulat suivant :

Les distances aux sommets fixés (c'est-à-dire les sommets de $S$) sont minimales.

A chaque itération, le sommet temporaire de plus petite distance est transféré directement dans $S$ et l'on met à jour les distances de tous ses successeurs. La complexité temporelle de l'algorithme de Dijkstra sous cette forme simple est $O(n^2)$. En effet, à chaque étape, on transfère un nud de $\overline{S}$ vers $S$, ce qui nous fait $n$ itérations. A l'intérieur de chaque itération, on recherche le sommet de $\overline{S}$ qui possède la plus petite distance temporaire, opération en $O(n)$ dans le pire des cas. Toutefois, des structures de données performantes (telles que les Tas de Fibonnacci) permettent de rabaisser significativement cette complexité ( $O(m+n\log n)$).

Démonstration de l'algorithme : Elle se fait par récurrence sur la taille de $S$ avec les hypothèses suivantes :

1. $d(i)$ est minimale pour tout sommet $i\:\in\:S$
2. $d(j)$ est la longueur du plus court chemin ne passant que par des sommets de $S$ pour arriver en $j \: \in \: \overline{S}$.

Vérifions la validité de l'hypothèse pour $S\,=\,\{s\}$.

1. $d(s)=0$ par définition de l'origine des plus courts chemins. Or, cette distance est nécessairement minimale du fait de la non négativité des coûts sur les arcs.
2. Dans $\overline{S}$ les seuls sommets pour lesquels $d(.) \, < \, +\infty$ sont les sommets $k$ tels que $(s,\,k)\:\in\:E$ et pour lesquels $d(k)=c_{sk}$ et comme $s$ est le seul sommet appartenant à $S$, l'hypothèse est nécessairement vérifiée.

Vérifions l'hypothèse à une étape quelconque : Soit $i$ le sommet de $\overline{S}$ dont la distance temporaire est minimale. Comme il va être transféré dans $S$, il nous faut montrer que $d(i)$ est optimale. Par hypothèse, $d(i)$ est la longueur d'un plus court chemin de $s$ vers $i$ dont tous les sommets intermédiaires appartiennent à $S$. Nous allons montrer que tout chemin qui utilise au moins un sommet de $\overline{S}$ est au moins aussi long. Soit $P$ un chemin de $s$ vers $i$ passant par des sommets de $\overline{S}$. On peut le décomposer en 2 sous chemins $P_1$ et $P_2$ où $P_1$ ne passe que par des sommets de $S$ et aboutit en $k\:\in\:\overline{S},\;\;k\,\neq\,i$ ; $P_2$ joignant $k$ à $i$ tel qu'illustré par la figure (3.2).

Figure 3.2: Mise en place de la démonstration de l'algorithme de Diksktra

Par hypothèse, $c(P_1) \, \geqslant \, d(k)$ car $d(k)$ est la longueur du plus court chemin ne passant que par des sommets de $S$ et aboutissant en $k$ alors que $P_1$ est un chemin quelconque ne passant que par des sommets de $S$ et aboutissant également en $k$. Or :

$$d(k) \, \geqslant \, d(i)$$

car $d(i)$ est minimale sur $\overline{S}$ (il s'agit de la base même de l'algorithme de Dijkstra). Et, comme :

$$c(P)\,=\,c(P_1)\,+\,c(P_2)$$   et$$\quad c(P_2)\, \geqslant \, 0$$

du fait de la non négativité des coûts portés par les arcs, l'on obtient :

$$c(P) \, \geqslant \, c(P_1) \, \geqslant \, d(i)$$

Finalement :

$$c(P) \, \geqslant \, d(i)$$

$d(i)$ est donc minimale pour tous les chemins passant par $S$ et $\overline{S}$. Elle est donc minimale globalement. Ouf ! Il nous faut maintenant vérifier que l'opération de mise à jour des distances et du tableau des prédécesseurs (c'est-à-dire, en fait, des chemins eux mêmes) est correcte. Les seuls sommets à être mis à jour sont $i$ et les sommets $k$ de $\overline{S}$ tels que $(i,\,k) \: \in \: E$ et $d(k)\,>\,d(i)\,+\,c_{ik}$. Or ces sommets $k$ auront pour prédécesseur $i$ qui fait partie de $S$. Donc leur distance temporaire est maintenant égale à $d(i)+c_{ik}$ ce qui constitue bien un plus court chemin empruntant uniquement des sommets de $S$.