Preuve de correction de Dijkstra par récurrence

1. La Stratégie de Preuve : Invariant de Boucle et Récurrence

La preuve de correction de l'algorithme de Dijkstra s'articule autour d'un invariant de boucle. L'idée est de démontrer qu'une certaine propriété reste vraie à chaque itération de la boucle principale de l'algorithme.

Partitionnons les sommets du graphe $V$ en deux ensembles à tout moment de l'exécution :

• $S$ : l'ensemble des sommets dont la distance la plus courte depuis la source $s$ a été finalisée.
• $V\setminus S$ : l'ensemble des sommets "frontière", pour lesquels on a une estimation de distance, mais pas encore la certitude que ce soit la plus courte.

L'invariant que nous allons prouver par récurrence sur la taille de $S$ est le suivant :

Invariant : Pour tout sommet $v\in S$, la distance calculée par l'algorithme, notée $d[v]$, est égale à la distance réelle du plus court chemin de $s$ à $v$, notée $\delta (s,v)$.

La preuve par récurrence se déroule en deux temps :

1. Initialisation (Cas de base) : Au début, $S=\{s\}$ et $d[s]=0$. La propriété est vraie, car le plus court chemin de la source à elle-même est de longueur 0.
2. Conservation (Étape de récurrence) : Supposons que l'invariant est vrai pour un ensemble $S$ de taille $k\ge 1$. L'algorithme choisit un sommet $u\in V\setminus S$ qui minimise $d[u]$ et l'ajoute à $S$. Nous devons prouver que pour ce nouveau sommet $u$, on a bien $d[u]=\delta (s,u)$.

2. Le Cœur de la Preuve : L'Étape de Récurrence

C'est ici que se trouve le nœud de la démonstration. Pour prouver que $d[u]=\delta (s,u)$, nous allons utiliser un raisonnement par l'absurde.

Supposons le contraire : $d[u]>\delta (s,u)$.
(Note : $d[u]$ ne peut pas être inférieur à $\delta (s,u)$ car l'algorithme ne construit que des chemins valides, donc les distances estimées sont toujours des majorants des distances réelles).

1. S'il existe un chemin plus court vers $u$ que celui de longueur $d[u]$, considérons ce chemin. Appelons-le $P$. Ce chemin $P$ part de $s$ (qui est dans $S$) et arrive à $u$ (qui est dans $V\setminus S$).

2. Il doit donc exister un premier sommet sur ce chemin $P$ qui n'est pas dans $S$. Traversons le chemin $P$ depuis $s$. Soit $(y,x)$ le premier arc du chemin tel que $y\in S$ et $x\in V\setminus S$.

3. Le chemin $P$ peut être décomposé : $s⇝y\to x⇝u$.
   La longueur du plus court chemin jusqu'à $u$, $\delta (s,u)$, est la longueur de ce chemin $P$.

   $$\delta (s,u)=\ell (s⇝y)+w(y,x)+\ell (x⇝u)$$

   Puisque les poids sont non-négatifs, $\ell (x⇝u)\ge 0$.
   De plus, la portion du chemin de $s$ à $y$ est elle-même un plus court chemin vers $y$ (propriété de sous-structure optimale). Donc, $\ell (s⇝y)=\delta (s,y)$.

4. Par notre hypothèse de récurrence, comme $y\in S$, nous savons que $d[y]=\delta (s,y)$.

5. Quand l'algorithme a finalisé le sommet $y$, il a relâché tous ses arcs sortants, y compris $(y,x)$. À ce moment-là (ou peut-être avant, via un autre chemin), la distance $d[x]$ a été mise à jour. Nous sommes donc certains que :

   $$d[x]\le d[y]+w(y,x)$$

6. Combinons ces éléments :

   $$d[x]\le d[y]+w(y,x)=\delta (s,y)+w(y,x)=\ell (s⇝y\to x)\le \ell (P)=\delta (s,u)$$

   Nous avons donc $d[x]\le \delta (s,u)$.

7. Maintenant, rappelons notre hypothèse de départ (par l'absurde) : $\delta (s,u)<d[u]$. En combinant avec le point précédent, on obtient :

   $$d[x]<d[u]$$

   Nous avons trouvé un sommet $x\in V\setminus S$ tel que $d[x]<d[u]$.

8. Ceci est une contradiction. L'algorithme de Dijkstra choisit justement le sommet de $V\setminus S$ qui a la plus petite distance $d$. Il aurait dû choisir $x$ (ou un autre sommet encore plus proche) et non $u$.

Notre supposition initiale était donc fausse. Il est impossible que $d[u]>\delta (s,u)$. Par conséquent, $d[u]=\delta (s,u)$, ce qui achève notre étape de récurrence et prouve la correction de l'algorithme.

3. Formalisation et Visualisation de la Preuve

Maintenant que nous avons déconstruit la logique, étudions comment cette preuve est présentée de manière formelle.

La vidéo suivante expose ce raisonnement de façon très claire et dynamique. Elle utilise la même structure de preuve par contradiction, en supposant l'existence d'un premier sommet pour lequel l'algorithme commettrait une erreur.

Pour une formalisation écrite, typique de ce qui est attendu pour l'Agrégation, le document suivant est une excellente référence. Il structure l'algorithme de manière explicitement récursive.

4. L'Importance Cruciale des Poids Non-Négatifs

Notre preuve repose de manière critique sur l'hypothèse des poids non-négatifs. Identifions où exactement.

L'étape clé est l'inégalité : $\delta (s,u)=\ell (s⇝x⇝u)\ge \ell (s⇝x)$.
Nous avons affirmé que $\ell (x⇝u)\ge 0$. Si un poids négatif était autorisé sur ce segment de chemin, la longueur totale du chemin pourrait être inférieure à celle de son préfixe.

Un arc à poids négatif pourrait créer un "raccourci" vers un sommet déjà finalisé, invalidant la décision gloutonne de l'algorithme. La vidéo suivante illustre parfaitement ce point.

Conclusion

La maîtrise de la preuve de correction de l'algorithme de Dijkstra est une étape importante. Elle solidifie votre compréhension de l'interaction entre l'approche gloutonne, les structures de données et les propriétés mathématiques du problème.

Points clés à retenir :

• La correction de l'algorithme de Dijkstra se prouve par récurrence sur la taille de l'ensemble $S$ des sommets finalisés.
• L'invariant essentiel est que pour tout sommet $v\in S$, la distance calculée $d[v]$ est la vraie distance minimale $\delta (s,v)$.
• L'étape de récurrence se démontre élégamment par l'absurde, en montrant qu'un chemin supposé plus court contredirait la règle de sélection de l'algorithme.
• L'hypothèse des poids non-négatifs est fondamentale pour garantir qu'un chemin ne peut pas devenir "meilleur" en s'allongeant.

Dans notre prochaine leçon, nous aborderons la question inévitable : comment gérer les graphes avec des poids négatifs ? Nous étudierons l'algorithme de Bellman-Ford, qui lève cette contrainte au prix d'une complexité plus élevée, et qui nous permettra également de détecter la présence de cycles de poids négatif.