Algorithme de Dijkstra — plus court chemin étape par étape

L’algorithme de Dijkstra trouve les plus courts chemins à partir d’un nœud de départ dans un graphe pondéré, tant que tous les poids des arêtes sont non négatifs. Si vous ne vous intéressez qu’à une seule destination, vous pouvez vous arrêter dès que cette destination est validée.

L’idée centrale est gloutonne : on continue toujours à partir du nœud non validé dont la distance connue est la plus petite. Cela ne fonctionne que si les poids sont tous non négatifs.

Ce que résout l’algorithme de Dijkstra

Utilisez l’algorithme de Dijkstra lorsque vous avez un graphe avec des coûts sur les arêtes et que vous cherchez l’itinéraire le moins coûteux. Le coût peut représenter une distance, un temps de trajet, une énergie, ou toute autre quantité que vous voulez minimiser.

Il fonctionne sur des graphes orientés ou non orientés. La condition essentielle est claire : chaque poids d’arête doit être au moins égal à $0$.

Comment fonctionne l’algorithme

Chaque nœud conserve une distance provisoire depuis le nœud de départ. Au début, le nœud de départ a la distance $0$ et tous les autres nœuds ont la distance $\infty$.

On répète ensuite cette boucle :

1. Choisir le nœud non validé avec la plus petite distance provisoire.
2. Examiner chacun de ses voisins en passant par ce nœud.
3. Si le nouveau chemin coûte moins cher, mettre à jour la distance du voisin.
4. Marquer le nœud courant comme validé.

L’étape 3 s’appelle la relaxation. Un nœud validé est terminé : sa plus courte distance est définitive, à condition que le graphe n’ait pas d’arêtes de poids négatif.

Algorithme de Dijkstra étape par étape

Voici la procédure complète sous forme compacte :

1. Choisir un nœud de départ.
2. Mettre sa distance à $0$ et toutes les autres distances à $\infty$.
3. Sélectionner le nœud non validé avec la plus petite distance provisoire.
4. Relâcher ses arêtes sortantes.
5. Marquer ce nœud comme validé.
6. Répéter jusqu’à ce que tous les nœuds atteignables soient validés, ou s’arrêter dès que le nœud cible est validé.

Si vous mémorisez aussi quel nœud précédent a provoqué chaque mise à jour, vous pouvez retrouver le chemin lui-même, et pas seulement la distance finale.

Exemple détaillé de plus court chemin

Supposons que le graphe ait les poids d’arêtes suivants :

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

Nous voulons le plus court chemin de $A$ à $D$.

On commence avec :

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

On valide d’abord $A$ et on relâche ses arêtes :

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

La plus petite distance non validée est maintenant celle de $C$, donc on valide ensuite $C$.

En passant par $C$ :

• Par $C$, le chemin vers $B$ coûte $1+2=3$, ce qui améliore $4$, donc on met à jour $\text{dist}(B)=3$.
• Par $C$, le chemin vers $D$ coûte $1+5=6$, donc on fixe $\text{dist}(D)=6$.

Maintenant, $B$ a la plus petite distance non validée, donc on valide $B$.

En passant par $B$, le chemin vers $D$ coûte :

$$3+1=4$$

Cela améliore $6$, donc on met à jour $\text{dist}(D)$ de $6$ à $4$.

Maintenant, $D$ est le nœud non validé avec la plus petite distance. On le valide, puis on s’arrête.

Le plus court chemin est :

$$A \to C \to B \to D$$

avec un coût total de :

$$1+2+1=4$$

Cet exemple montre le schéma essentiel : un trajet qui semblait d’abord moins bon, $A \to B$, est devenu meilleur plus tard en passant par $C$. L’algorithme de Dijkstra l’autorise tant que $B$ n’est pas encore validé. Une fois qu’un nœud est validé, sa distance ne changera plus.

Pourquoi les poids non négatifs sont importants

Supposons que le nœud non validé actuellement le moins coûteux ait la distance $d$. Tout nouveau chemin vers ce nœud trouvé plus tard devrait venir d’un autre nœud non validé dont la distance provisoire est au moins $d$, puis ajouter une arête de poids au moins égal à $0$.

Donc ce chemin trouvé plus tard ne peut pas faire mieux que $d$. C’est pourquoi valider la plus petite distance provisoire est sûr lorsque tous les poids sont non négatifs.

S’il existe une arête négative, cet argument ne tient plus. Un chemin qui semble coûteux maintenant peut devenir moins cher plus tard, ce qui signifie que valider un nœud trop tôt peut donner une mauvaise réponse.

Erreurs fréquentes avec l’algorithme de Dijkstra

L’utiliser avec une arête négative

Même une seule arête négative peut casser la logique gloutonne. Si des poids négatifs sont possibles, utilisez une autre méthode de plus court chemin.

Confondre « vu » et « terminé »

Un nœud peut déjà avoir une distance provisoire tout en n’étant pas terminé. Seul un nœud validé a une plus courte distance définitive.

Oublier la table des prédécesseurs

Les distances donnent le coût. Si vous voulez aussi l’itinéraire lui-même, stockez quel nœud a amélioré en dernier chaque distance.

Où l’algorithme de Dijkstra est utilisé

L’algorithme de Dijkstra est utilisé lorsqu’un problème peut être modélisé comme un déplacement dans un graphe à coûts non négatifs :

• Calcul d’itinéraires sur des cartes
• Routage réseau
• Déplacement de robots sur des grilles pondérées
• Pathfinding dans les jeux lorsque les coûts de déplacement varient

C’est aussi un exemple classique d’algorithme glouton dont la validité dépend d’une condition précise.

Essayez un problème similaire

Dessinez un graphe à cinq nœuds avec des poids d’arêtes positifs, puis exécutez l’algorithme de Dijkstra à la main avec une table de distances. Pour aller plus loin, essayez votre propre version sur un nouveau graphe et vérifiez exactement à quel moment chaque nœud peut être validé en toute sécurité.