- Escale actuelle
- Déjà une escale
- Paire raccourcie
- Chemin
Algorithme de Floyd–Warshall
Quelle distance sépare chaque ville de toutes les autres ? Floyd–Warshall répond d'un coup, avec un tableau et trois boucles imbriquées. Chaque tour autorise un nœud de plus comme escale et demande, pour chaque paire, si le détour par lui est plus court. Avancez pas à pas pour voir le tableau se remplir et les distances baisser. Appuyez sur Lecture pour voir le tableau se remplir, ou sur Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où. Le tableau contient la plus courte distance trouvée jusqu'ici entre chaque paire de nœuds ; le nombre sur chaque arête est sa longueur. Chaque tour autorise un nœud de plus comme escale en chemin, et chaque étape montre une paire qui raccourcit en passant par lui. Cliquez sur un nœud pour en faire le départ ; basculez le clic sur Cible et cliquez sur un autre nœud pour voir à la fin le plus court chemin entre eux. Nouveau graphe crée un autre graphe ; choisissez son nombre de nœuds et d'arêtes. Quand le plateau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.
Comment ça marche
- Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où.
- Observez le tableau : la ligne et la colonne de l'escale actuelle sont teintées, et chaque étape inscrit une distance plus courte.
- Choisissez un départ et une cible pour voir à la fin le plus court chemin entre eux. Nouveau graphe crée un autre graphe à essayer.
Fonctionnement de Floyd–Warshall
Faites un tableau avec une ligne et une colonne par nœud. Inscrivez 0 sur la diagonale, la longueur de l'arête là où deux nœuds sont reliés, et l'infini partout ailleurs. Prenez ensuite chaque nœud k à tour de rôle comme escale possible. Pour chaque paire i, j, comparez la distance de i à j dans le tableau avec la distance de i à k plus la distance de k à j, et gardez la plus petite. Après le dernier nœud, chaque case est la plus courte distance entre ses deux nœuds.
Pourquoi ça marche
Après le tour de k, le tableau contient, pour chaque paire, le plus court chemin dont toutes les escales sont parmi les nœuds déjà traités. Le tour du nœud suivant doit seulement décider si ce nœud aide : un plus court chemin qui passe par lui est un plus court chemin jusqu'à lui plus un plus court chemin depuis lui, tous deux déjà dans le tableau. Cette façon de construire une grande réponse à partir de plus petites déjà trouvées s'appelle la programmation dynamique. Avec des arêtes négatives, la méthode marche encore, et un nombre négatif sur la diagonale révèle un cycle négatif.
Questions fréquemment posées
Qu'est-ce que l'algorithme de Floyd–Warshall ?
Un algorithme qui trouve la plus courte distance entre chaque paire de nœuds d'un graphe pondéré. Il tient un tableau des distances et, pour chaque nœud à tour de rôle, vérifie si passer par ce nœud raccourcit une paire.
Floyd–Warshall est-il rapide ?
Il a trois boucles imbriquées sur les n nœuds, donc le travail croît comme n³, et le tableau a besoin de n² cases. Cela convient pour des graphes de quelques centaines de nœuds. Pour de grands graphes peu denses, lancer l'algorithme de Dijkstra depuis chaque nœud est plus rapide.
Floyd–Warshall gère-t-il les arêtes négatives ?
Oui, tant qu'il n'y a pas de cycle négatif. S'il y en a un, une case de la diagonale devient négative, et c'est ainsi que Floyd–Warshall le détecte.
Comment obtenir les chemins, et pas seulement les distances ?
Tenez un second tableau avec le nœud suivant sur le chemin de i à j. Chaque fois qu'une paire raccourcit en passant par k, copiez le nœud suivant de i vers k. En suivant ce tableau de i à j, on obtient le chemin.
Mon graphe est-il envoyé quelque part ?
Non. Le graphe est créé et le tableau rempli dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur