Dijkstra et Bellman-Ford partent d'une source. Un service qui reçoit beaucoup de demandes entre des points différents peut vouloir connaître toutes les distances à l'avance. Floyd-Warshall remplit une matrice contenant une réponse pour chaque couple départ–arrivée. Son fonctionnement tient dans une comparaison répétée, mais le sens de ses étapes doit être compris pour éviter une erreur classique sur l'ordre des boucles.
Le résultat prend déjà une place proportionnelle à n² si l'on conserve chaque couple. Cette dépense est justifiée lorsque les requêtes sont nombreuses, mais peut être excessive pour une seule destination. Avant de choisir Floyd-Warshall, il faut donc évaluer le nombre de sommets et le besoin réel de toutes les réponses.
Nous utilisons un exemple orienté plus petit pour lire les matrices sans surcharge. Les sommets sont A, B, C et D. Les arcs sont AB de poids 3, AD de poids 10, BC de poids −2, CD de poids 2 et DB de poids 4. Les poids négatifs sont autorisés ; le graphe ne contient pas de cycle négatif.
La matrice de départ contient zéro sur la diagonale, le poids de l'arc lorsqu'il existe et l'infini sinon. S'il existe plusieurs arcs de mêmes extrémités, on garde le poids minimal. En présence d'une boucle négative, la diagonale doit en tenir compte au lieu de l'écraser par zéro : le cycle négatif existe déjà dans les données.
| Départ / arrivée | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 3 | ∞ | 10 |
| B | ∞ | 0 | -2 | ∞ |
| C | ∞ | ∞ | 0 | 2 |
| D | ∞ | 4 | ∞ | 0 |
La case AD vaut initialement 10, car l'arc direct existe. La case AC vaut l'infini, car aucun arc direct ne relie A à C. Cela ne signifie pas que C restera inaccessible : un parcours utilisant B peut changer la réponse. La matrice initiale ne connaît simplement aucun intermédiaire autorisé.
La comparaison n'est valable que si les deux morceaux sont accessibles. On ne doit pas additionner une valeur sentinelle représentant l'infini à un nombre ordinaire. En l'absence de cycle négatif, un trajet optimal peut être choisi sans répétition inutile : le découpage au passage par k suffit à décrire les possibilités pertinentes.
Initialiser D avec les trajets directs et la diagonale
Pour chaque sommet k, dans l'ordre choisi :
Pour chaque départ i :
Pour chaque arrivée j :
Si D[i, k] et D[k, j] sont finis :
Si D[i, k] + D[k, j] < D[i, j] :
D[i, j] ← D[i, k] + D[k, j]
actualiser les informations de reconstructionLa boucle sur k doit rester à l'extérieur dans cette version. Elle définit ce que signifient les solutions disponibles avant une étape. Changer librement l'ordre des trois boucles détruit cette garantie ; une suite de comparaisons qui ressemble à la formule n'est pas automatiquement le même algorithme.
Autoriser A ne change aucune distance. Autoriser B crée AC à 1 grâce à 3 + (−2), et DC à 2 grâce à 4 + (−2). Autoriser C améliore AD à 3 et BD à 0. Enfin, autoriser D crée CB à 6. Ces modifications proviennent de chemins autorisés, pas d'une symétrie supposée.
| Départ / arrivée | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 3 | 1 | 3 |
| B | ∞ | 0 | -2 | 0 |
| C | ∞ | 6 | 0 | 2 |
| D | ∞ | 4 | 2 | 0 |
La distance de A vers D devient donc 3 par A–B–C–D, alors que l'arc direct coûtait 10. La distance de C vers B vaut 6 par C–D–B. Les cases BA, CA et DA restent à l'infini : aucun arc n'entre dans A, donc aucun de ces départs ne peut l'atteindre.
Les zéros de la diagonale correspondent aux trajets vides, qui restent optimaux ici. Le circuit B–C–D–B coûte −2 + 2 + 4 = 4 ; le répéter ne peut pas améliorer un coût. Le signe négatif d'un seul arc ne suffit donc pas à invalider l'exemple. Les matrices intermédiaires sont calculées par le même programme que celui qui produit le schéma.
Pour un arc direct, le prochain sommet est son arrivée. Lorsque AD s'améliore par C, son premier pas reste celui du meilleur trajet de A vers C, donc B. On poursuit ensuite depuis B vers la même destination D. La reconstruction s'arrête à D et ne demande pas de recalculer les distances.
Si une case diagonale D[k, k] devient négative, un cycle négatif existe. Pour un couple i, j, le coût est non borné si i peut atteindre un tel k et si k peut atteindre j. Il faut alors marquer ce statut plutôt que présenter une valeur finie issue du tableau. Les autres couples peuvent conserver une distance finie ou rester inaccessibles.
Un mécanisme de reconstruction doit refuser ces couples affectés et les couples inaccessibles. Une suite de pointeurs tournant dans un cycle n'est pas une réponse acceptable. Les contrôles sur la diagonale et l'accessibilité font donc partie de l'interprétation du résultat, pas d'un détail facultatif d'affichage.
Les trois boucles parcourent chacune les sommets : le temps est O(n³). La matrice demande O(n²) de mémoire. Le tableau des prochains sommets ajoute un autre tableau de même ordre. On peut effectuer les mises à jour des distances en place dans la version standard ; conserver chaque matrice intermédiaire sert à expliquer le calcul, mais augmente la mémoire utilisée.
Le coût ne dépend pas directement du nombre d'arcs une fois la matrice construite. C'est pratique pour un graphe dense de taille raisonnable, moins pour un immense graphe clairsemé. Sur des poids non négatifs, lancer Dijkstra depuis chaque source peut mieux exploiter des listes d'adjacence. Avec des poids négatifs, d'autres méthodes existent, mais demandent des hypothèses et des transformations supplémentaires.
Pour vérifier une implantation, on peut comparer chaque ligne finale à un Bellman-Ford lancé depuis la source correspondante, sur un exemple sans cycle négatif. Il faut conserver le sens des arcs, les poids et les conventions d'infini identiques. Cette comparaison indépendante est plus convaincante que vérifier seulement que la diagonale contient des zéros.
Pour approfondir la formulation par intermédiaires, les notes de cours du MIT sur les plus courts chemins toutes paires présentent la justification formelle. Notre exemple et nos schémas sont originaux et recalculés.
Avec AB = 3 et BC = −2, quelle proposition obtient-on pour AC quand B devient autorisé ?
On obtient 3 + (−2) = 1. Cette valeur remplace l'infini initial de AC. Il s'agit d'un trajet orienté A–B–C ; la mise à jour n'autorise aucune déduction automatique sur CA.
Pourquoi AD finit-il à 3 malgré l'arc direct de poids 10 ?
Le trajet A–B–C–D coûte 3 − 2 + 2 = 3. La formule conserve le minimum entre la liaison directe et les trajets indirects autorisés. La présence d'un arc direct n'impose pas de l'utiliser.
Pourquoi la ligne de B conserve-t-elle l'infini dans la colonne A ?
Aucun arc n'entre dans A. Il est donc impossible de terminer un trajet partant de B en A. L'infini décrit une absence de parcours, et non un coût dépassant une limite d'affichage.
Peut-on déplacer la boucle sur k à l'intérieur simplement pour rapprocher les écritures mémoire ?
Pas dans la version standard présentée. Les étapes supposent que seuls les intermédiaires déjà autorisés ont été exploités. Modifier l'ordre exige une autre démonstration ou une transformation correcte ; la ressemblance de la formule ne suffit pas.
Questions / Réponses
Ajouter un commentaire