AnalyseMéthode · Glossaire
algorithme de Ford
L'algorithme de Ford est un algorithme de recherche de plus court chemin dans un graphe pondéré orienté, relevant de la théorie des graphes. Sa caractéristique principale est de traiter les graphes dont certains arcs ont des valuations négatives, cas que d'autres algorithmes classiques ne gèrent pas. Il permet de calculer, depuis un sommet source donné, le plus court chemin vers chaque sommet accessible, même en présence de poids d'arcs négatifs, à condition qu'aucun circuit négatif accessible depuis la source ne permette de rejoindre le sommet concerné.
Sommaire
Ce que vous allez apprendre
- Relier la relaxation d’un arc à l’amélioration d’une distance.
- Refaire un calcul sur quatre sommets avec un arc de poids négatif.
- Reconnaître un circuit négatif accessible et un sommet inaccessible.
- Distinguer Ford de Dijkstra et de Ford-Fulkerson.
En clair
Imaginez quatre villes reliées par des routes à sens unique. Chaque route porte un coût, et un coût négatif représente un gain qui compense une partie du trajet. L’algorithme de Ford part d’une ville source et améliore peu à peu le meilleur coût connu pour atteindre chacune des autres.
À chaque amélioration, il propage la nouvelle valeur le long des routes suivantes. Les coûts négatifs sont donc admis, mais un circuit négatif accessible depuis la source empêcherait l’existence d’un coût minimal fini pour les villes que l’on peut atteindre depuis ce circuit. Les autres peuvent conserver un coût minimal fini.
Définition
L’algorithme de Ford calcule les distances minimales finies depuis un sommet source dans un graphe orienté dont chaque arc porte un poids réel, pour les sommets accessibles qu’aucun circuit négatif accessible depuis la source ne permet de rejoindre. Le poids d’un chemin est la somme des poids de ses arcs. Une distance vaut d’abord 0 pour la source et l’infini pour les autres sommets. Un poids d’arc peut être négatif.
Pour un arc allant du sommet u au sommet v, de poids w(u, v), une relaxation compare la distance actuelle de v au coût obtenu en passant par u : . Les arcs sont relaxés à plusieurs reprises. Si le graphe contient n sommets et qu’aucun circuit de poids négatif n’est accessible depuis la source, n − 1 passages complets suffisent. Un passage supplémentaire qui améliore encore une distance révèle un tel circuit.
Le résultat associe à chaque sommet accessible le poids minimal d’un chemin issu de la source. Un sommet inaccessible conserve une distance infinie. En mémorisant, lors de chaque amélioration, le sommet précédent, on peut aussi reconstruire les chemins obtenus.
Le principe
Initialisez la distance de la source à 0 et toutes les autres à l’infini. Pour chaque arc u → v, remplacez la distance de v par le plus petit nombre entre sa valeur actuelle et la distance de u augmentée du poids de l’arc. Répétez sur tous les arcs jusqu’à ce qu’aucune valeur ne change, sans dépasser n − 1 passages pour un graphe à n sommets. Si un passage supplémentaire produit encore une baisse, un circuit négatif est accessible et les distances minimales finies ne sont pas toutes définies.
Quand l'utiliser
La méthode demande un graphe orienté, un sommet source et un poids numérique pour chaque arc. Les poids peuvent être positifs, nuls ou négatifs. Le calcul porte uniquement sur les sommets accessibles depuis la source, et le sens de chaque arc doit être respecté.
Pour obtenir une distance minimale finie vers un sommet, aucun circuit de poids total négatif accessible depuis la source ne doit permettre de rejoindre ce sommet. Sinon, chaque tour du circuit réduit encore le coût. L’algorithme doit alors signaler ce contre-cas au lieu d’annoncer un plus court chemin. Un sommet isolé ou placé dans une composante inaccessible reste simplement à distance infinie.
Un exemple, pas à pas
Considérons les sommets S, A, B et C. La source est S. Les arcs pondérés sont S → A de poids 4, S → B de poids 5, A → B de poids −2, A → C de poids 4 et B → C de poids 3. La figure rend visibles ces cinq données et le chemin finalement retenu vers C.
1. Au départ, les distances de S, A, B et C sont respectivement 0, ∞, ∞ et ∞.
2. Les arcs issus de S donnent 4 pour A et 5 pour B.
3. L’arc A → B améliore B, car 4 + (−2) = 2, inférieur à 5.
4. L’arc A → C donne d’abord 4 + 4 = 8 pour C.
5. L’arc B → C améliore C, car 2 + 3 = 5, inférieur à 8.
2. Les arcs issus de S donnent 4 pour A et 5 pour B.
3. L’arc A → B améliore B, car 4 + (−2) = 2, inférieur à 5.
4. L’arc A → C donne d’abord 4 + 4 = 8 pour C.
5. L’arc B → C améliore C, car 2 + 3 = 5, inférieur à 8.
Les distances finales sont 0 pour S, 4 pour A, 2 pour B et 5 pour C. Le plus court chemin de S à C est S → A → B → C, de poids 4 − 2 + 3 = 5. Un nouveau passage ne change aucune valeur : ce contrôle confirme le point d’arrêt sur cet exemple.
En pratique
Dans un réseau orienté, on traduit chaque liaison possible par un arc et son coût par un poids. Ford est pertinent dès qu’un avantage, un crédit ou une correction peut rendre certains poids négatifs.
Avant le calcul, il faut fixer la source et vérifier le sens des arcs. Après le calcul, on examine les distances et les prédécesseurs pour retrouver un itinéraire minimal, pas seulement son coût.
Si tous les poids sont non négatifs, un algorithme conçu pour ce cas peut être préféré. Si une relaxation reste possible après n − 1 passages, on ne force pas un résultat : on signale le circuit négatif accessible.
À ne pas confondre
Avec l’algorithme de Dijkstra. Dijkstra repose sur des poids non négatifs, tandis que Ford accepte des arcs négatifs. Dans l’exemple, l’arc A → B de poids −2 est précisément le cas qui impose cette distinction.
Avec l’algorithme de Ford-Fulkerson. Ford cherche ici des plus courts chemins depuis une source. Ford-Fulkerson traite un problème de flot maximal dans un réseau muni de capacités ; le résultat recherché n’est donc pas une distance.
Limites et pièges
Circuit négatif accessible. Si une distance baisse encore après n − 1 passages, le symptôme n’est pas un calcul inachevé : le coût peut diminuer sans borne en parcourant le circuit. Il faut signaler l’absence de minimum fini pour les sommets concernés.
Circuit négatif inaccessible. Un circuit négatif situé dans une partie que la source ne peut pas atteindre ne remet pas en cause les distances calculées depuis cette source. Il faut tester l’accessibilité avant de généraliser l’alerte à tout le graphe.
Sommet inaccessible. Une distance restée à ∞ ne signifie pas que le chemin est très coûteux. Elle signifie qu’aucun chemin orienté ne relie la source à ce sommet ; aucun prédécesseur ne doit alors être reconstruit.
Arrêt anticipé. Si un passage complet ne modifie aucune distance, les passages restants sont inutiles. Dans l’exemple à quatre sommets, trois passages constituent la borne, mais la stabilité des valeurs autorise un arrêt plus tôt.
Pour aller plus loin
La relaxation est l’idée à prolonger : une information locale portée par un arc améliore progressivement une information globale sur les chemins. On peut ensuite étudier l’influence de l’ordre des relaxations, la reconstruction des chemins par les prédécesseurs et la manière dont un circuit négatif propage l’absence de minimum fini.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres