algorithme de Moore-Dijkstra

Imaginez un plan où chaque route porte un coût : une distance, une durée ou un prix. Depuis le départ, on inscrit d'abord le meilleur coût connu pour chaque lieu voisin. On choisit ensuite le lieu encore disponible dont le coût est le plus petit, puis on regarde si passer par lui améliore les autres trajets.

Avec des coûts non négatifs, le lieu choisi ne pourra plus être atteint à moindre coût par un détour ultérieur. En répétant ce geste, l'algorithme de Moore-Dijkstra construit les plus courtes distances depuis le départ.

L'algorithme de Moore-Dijkstra est une procédure de recherche de plus courts chemins dans un graphe valué. Les sommets représentent les positions possibles, les arêtes représentent les passages et chaque arête porte un poids non négatif. Un sommet de départ est fixé. À chaque sommet, l'algorithme associe une distance provisoire : zéro au départ, et une valeur indéfiniment grande ailleurs.

Parmi les sommets non encore fixés, la procédure choisit celui dont la distance provisoire est minimale. Elle examine chacune de ses arêtes : si le trajet passant par ce sommet coûte moins cher que la valeur déjà connue pour le voisin, cette valeur et le prédécesseur correspondant sont remplacés. Le sommet choisi est alors fixé. Les prédécesseurs permettent de reconstruire un chemin, et pas seulement d'en connaître le coût.

La procédure s'arrête dès que la destination est fixée si une seule destination est recherchée. Elle peut aussi continuer jusqu'à fixer tous les sommets atteignables afin d'obtenir toutes les distances depuis le départ. La non-négativité des poids justifie le caractère définitif d'une distance fixée.

On note d(v) le meilleur coût connu du départ au sommet v, et w(u,v) le poids de l'arête reliant le sommet fixé u à son voisin v. Initialisez la distance du départ à 0 et les autres à une valeur indéfiniment grande.

Choisissez un sommet u non fixé de distance minimale, puis appliquez à chaque voisin v la mise à jour suivante : Si la seconde valeur est retenue, mémorisez u comme prédécesseur de v. Fixez u, puis recommencez jusqu'à fixer la destination ou épuiser les sommets atteignables.

La méthode prend comme données un graphe valué, un sommet de départ et, éventuellement, une destination. Chaque poids doit être non négatif, et les poids comparés doivent exprimer un même coût. Elle renvoie le coût minimal vers chaque sommet atteint ainsi qu'un prédécesseur permettant de retrouver le trajet.

Si une arête porte un poids négatif, un sommet déjà fixé peut recevoir plus tard un meilleur coût : l'étape décisive n'est alors plus valide. Il faut employer une méthode de plus court chemin conçue pour accepter les poids négatifs. S'il n'existe aucun chemin depuis le sommet de départ jusqu'à la destination, sa distance reste indéfinie et aucun chemin n'est renvoyé.

On cherche le plus court trajet de A à E dans un réseau non orienté. Les arêtes ont les poids suivants : A–C vaut 2, A–B vaut 4, C–B vaut 1, C–D vaut 8, B–D vaut 5 et D–E vaut 2.

La figure représente exactement ce réseau. Les arêtes rouges formeront le trajet finalement retenu ; les nombres inscrits sur toutes les arêtes sont les coûts utilisés dans le calcul.

1. Depuis A, les coûts provisoires deviennent 2 pour C et 4 pour B.
2. C est fixé avec 2. Passer par C améliore B, car 2 + 1 = 3, et donne 2 + 8 = 10 pour D.
3. B est fixé avec 3. Passer par B améliore D, car 3 + 5 = 8.
4. D est fixé avec 8. Le coût provisoire de E devient 8 + 2 = 10.
5. E est fixé avec 10 : la recherche peut s'arrêter.

En remontant les prédécesseurs, on obtient E, D, B, C, A, donc le trajet A–C–B–D–E dans le sens du départ. Son coût est 2 + 1 + 5 + 2 = 10. Pour contrôler le choix, le détour A–C–D–E coûte 2 + 8 + 2 = 12, et A–B–D–E coûte 4 + 5 + 2 = 11.

Dans un réseau routier, les sommets sont des carrefours et les poids peuvent représenter des distances. La procédure compare les itinéraires possibles et conserve le plus court depuis le point de départ. Si le coût de certaines routes devient négatif, ce modèle et cette méthode ne conviennent plus.

Dans un réseau de télécommunications, un poids peut mesurer le coût choisi pour franchir une liaison. Le routage recherche alors une succession de liaisons de coût total minimal. Lorsque l'on veut les distances entre toutes les paires de sommets plutôt que depuis un seul départ, l'algorithme de Floyd constitue une autre organisation du calcul.

Dans un problème de transport, le geste essentiel consiste à définir d'abord ce que mesure un poids, puis à additionner uniquement des coûts comparables. Un trajet minimal en distance n'est pas nécessairement minimal en durée : changer le poids change la question résolue.

Algorithme de Moore-Dijkstra et algorithme de Floyd. Le premier part d'un sommet donné et étend les meilleures distances connues. Le second organise ensemble les distances entre toutes les paires de sommets. Pour chercher seulement les trajets issus de A dans un grand réseau à poids non négatifs, Moore-Dijkstra répond directement au besoin ; pour obtenir un tableau complet de toutes les paires, Floyd vise ce second résultat.

Plus court chemin et chemin comportant le moins d'arêtes. Moore-Dijkstra minimise la somme des poids, pas nécessairement le nombre de passages. Dans l'exemple, A–B utilise une seule arête de poids 4, tandis que A–C–B utilise deux arêtes mais ne coûte que 2 + 1 = 3.

Un poids négatif invalide la fixation. Le symptôme est qu'un détour découvert plus tard ferait baisser la distance d'un sommet déclaré définitif. Il faut arrêter la procédure et choisir un algorithme compatible avec ce type de poids.

Un sommet peut être inaccessible. Quand tous les sommets atteignables sont fixés mais que la destination conserve une distance indéfinie, il n'existe aucun chemin depuis le départ dans le graphe considéré. Il ne faut pas transformer cette absence en une très grande distance numérique.

Plusieurs chemins minimaux peuvent coexister. Si deux mises à jour donnent exactement le même coût, la distance minimale est unique comme valeur, mais le trajet ne l'est pas forcément. Pour tous les conserver, il faut mémoriser tous les prédécesseurs à égalité plutôt qu'un seul.

Le poids choisi détermine le sens de « plus court ». Additionner des kilomètres produit un minimum de distance ; additionner des durées produit un minimum de temps. Si les données mélangent ces grandeurs, la comparaison n'a pas de sens : il faut définir une mesure commune avant le calcul.

Trouver son chemin vite et bien prolonge la méthode par une réflexion sur la recherche efficace d'un itinéraire dans un graphe.

L'algorithme de Floyd élargit la question aux plus courts chemins entre toutes les paires de sommets.