Le trajet comportant le moins de relais n'est pas toujours le moins coûteux. Dans notre réseau, certaines petites liaisons permettent un détour avantageux. Dijkstra cherche le coût minimal depuis une source lorsque tous les poids sont positifs ou nuls. Son idée consiste à confirmer progressivement les distances, en expliquant pourquoi aucune route encore inconnue ne pourra les améliorer.
Au départ, la source A vaut zéro et les autres sommets valent l'infini. L'infini signifie « aucun trajet connu », pas « trajet très cher ». Chaque valeur finie provient d'un parcours réellement découvert. Une relaxation améliore donc une solution existante ; elle ne devine jamais une distance sans liaison pour la justifier.
Dans un graphe non orienté, on peut envisager chaque arête dans les deux sens. Dans un graphe orienté, seules les sorties de u sont candidates. La même formule sert dans les deux cas, mais l'ensemble des déplacements autorisés change. Il faut également conserver le parent au moment de l'amélioration, et non seulement lors de la première découverte comme dans BFS.
Dijkstra choisit toujours le sommet non finalisé dont la distance provisoire est la plus petite. Il finalise ce sommet puis examine ses sorties. La propriété essentielle porte sur les poids : ils doivent tous être positifs ou nuls. Elle garantit qu'un détour ajouté plus tard ne fera pas baisser le coût d'un trajet déjà confirmé.
d[source] ← 0 ; toutes les autres distances ← infini
Insérer (0, source) dans la file de priorité
Tant que la file n'est pas vide :
(clé, u) ← retirer le minimum
Si clé ne correspond plus à d[u] : ignorer cette entrée
Si u est déjà finalisé : continuer
finaliser u
Pour chaque sortie (u, v, poids) :
Si v n'est pas finalisé et d[u] + poids < d[v] :
améliorer d[v] ; parent[v] ← u
insérer (d[v], v)Une amélioration peut laisser une ancienne entrée dans la file. Le test de la clé élimine ces entrées périmées. Une autre implantation modifie directement la priorité de l'entrée existante. Les deux approches reposent sur le même raisonnement, mais leurs besoins en mémoire et les détails de leur complexité ne sont pas identiques.
A est finalisé en premier. Ses sorties donnent B à 4 et C à 2. C devient donc le prochain sommet traité. Le passage A–C–B améliore B à 3 ; C propose aussi D à 10 et E à 12. La découverte initiale de B n'était pas une confirmation : elle devait pouvoir être améliorée.
| Sommet finalisé | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| A | 0 | 4 | 2 | ∞ | ∞ | ∞ |
| C | 0 | 3 | 2 | 10 | 12 | ∞ |
| B | 0 | 3 | 2 | 8 | 12 | ∞ |
| D | 0 | 3 | 2 | 8 | 10 | 14 |
| E | 0 | 3 | 2 | 8 | 10 | 13 |
| F | 0 | 3 | 2 | 8 | 10 | 13 |
B est ensuite finalisé à 3 et améliore D à 8. D abaisse E à 10 et propose F à 14. E améliore finalement F à 13. L'ordre des finalisations est A, C, B, D, E, F. Les lignes du tableau montrent les distances après examen des sorties du sommet indiqué, pas avant son traitement.
Les parents finaux sont C depuis A, B depuis C, D depuis B, E depuis D et F depuis E. En remontant depuis F, on reconstruit A–C–B–D–E–F. Son coût vaut 2 + 1 + 5 + 2 + 3 = 13. Ce trajet est plus long en nombre d'arêtes que celui trouvé par BFS, mais moins coûteux.
Supposons que u, choisi au minimum, possède encore une route moins chère. Sur cette route, considérons le premier sommet non finalisé et son prédécesseur déjà finalisé. Lorsque ce prédécesseur a été traité, sa sortie a proposé un coût au premier sommet encore inconnu. Ce coût ne dépasse pas celui du trajet complet, puisque les poids restants sont non négatifs.
La file aurait donc contenu une distance plus petite que celle de u, contredisant le choix du minimum. Aucune route moins chère ne peut exister. C'est le rôle exact de l'hypothèse sur les poids : elle empêche la suite du trajet de diminuer un coût déjà accumulé.
Les égalités ne posent pas de problème de distance. Plusieurs sommets peuvent avoir la même priorité et plusieurs chemins minimaux peuvent exister. Notre convention alphabétique rend les traces stables. On ne change le parent que pour une amélioration stricte, afin de conserver une reconstruction simple, notamment en présence de liaisons de poids nul.
Considérons les arcs S → A de poids 2, S → B de poids 5 et B → A de poids −4. Depuis S, Dijkstra propose A à 2 et B à 5. Il finalise A avant B. Lorsque B est traité, le trajet S–B–A coûterait 1, mais A est déjà figé : la version étudiée conserve donc à tort la valeur 2.
Ce graphe ne contient pourtant aucun cycle. Le problème n'est pas une boucle infinie ; c'est la preuve de finalisation qui ne fonctionne plus. Bellman-Ford trouvera correctement la valeur 1. Certaines variantes de files qui rouvrent les sommets peuvent obtenir la bonne réponse sur cet exemple, mais cela ne restaure ni la preuve ni les garanties de Dijkstra classique.
Avec une sélection linéaire du minimum et une matrice, l'algorithme coûte O(n²). Avec des listes d'adjacence et un tas binaire permettant de diminuer une priorité, le coût devient O((n + m) log n), et la mémoire auxiliaire O(n). Le stockage du graphe reste à compter séparément.
Avec l'approche qui insère une nouvelle entrée à chaque amélioration, la file peut contenir O(m) entrées ; on obtient une borne O(n + m log(m + 1)) et une mémoire auxiliaire O(n + m). Pour un graphe simple, on emploie souvent la borne usuelle en log n. Annoncer le type de file évite de promettre une économie mémoire que l'implantation ne réalise pas.
On peut arrêter lorsqu'une cible est finalisée, pas lorsqu'elle est simplement découverte. Les sommets encore à l'infini après épuisement de la file sont inaccessibles. Pour les calculs machine, il faut aussi éviter le débordement lors d'une addition et rejeter les valeurs invalides. Des unités cohérentes et un contrôle préalable des poids font partie du contrat d'entrée.
C est finalisé avec d[C] = 2. Le poids CB vaut 1 et B était à 4. Que change l'algorithme ?
Le passage par C coûte 2 + 1 = 3, inférieur à 4. On met d[B] à 3 et parent[B] à C, puis on actualise sa priorité. B n'étant pas finalisé, cette amélioration est autorisée.
Pourquoi F passe-t-il de 14 à 13 après le traitement de E ?
D avait proposé 8 + 6 = 14 par DF. E possède ensuite la distance 10 et EF vaut 3. Le passage par E coûte 13 et remplace la proposition précédente ; le parent de F devient E.
Une cible vient d'être insérée dans la file. Peut-on déjà annoncer son coût minimal ?
Non. Une autre liaison peut améliorer sa distance avant son retrait au minimum. L'arrêt sûr intervient à sa finalisation. L'exemple de B, d'abord à 4 puis à 3, montre concrètement cette différence.
Retrouvez la vraie distance de A dans le contre-exemple et indiquez l'étape qui rend la version classique incorrecte.
S–B–A coûte 5 − 4 = 1. La version classique finalise pourtant A à 2 avant d'examiner B. Elle refuse ensuite de modifier ce sommet. C'est la finalisation prématurée, justifiée seulement avec des poids non négatifs, qui provoque l'erreur.
Questions / Réponses
Ajouter un commentaire