Plus courts chemins

Un GPS, un routeur, un jeu vidéo qui déplace un personnage : tous posent la même question, celle du trajet de coût minimal dans un graphe pondéré. Quand tous les poids sont positifs, un algorithme la résout en une passe, sans jamais revenir sur une décision. Quand un poids devient négatif, ce bel édifice s'effondre, et il faut autre chose. Ce chapitre traite les deux cas, et surtout la raison de la différence.

Deux notions de « plus court »

Le chapitre sur les parcours a déjà résolu un cas : quand toutes les arêtes se valent, le BFS donne le plus court chemin en nombre d'arêtes. Dès que les arêtes portent des poids, cette réponse ne suffit plus.

Définition

Dans un graphe pondéré, le poids d'un chemin est la somme des poids de ses arêtes, à ne pas confondre avec sa longueur, qui est son nombre d'arêtes. Un plus court chemin de $u$ à $v$ est un chemin de $u$ à $v$ de poids minimal : on dit « plus court » par habitude, même quand le poids est un temps ou un coût.

Ce poids minimal est la distance de $u$ à $v$ , notée $\mathrm{dist}(u, v)$ . Quand le départ est fixé, on écrit simplement $\mathrm{dist}(v)$ .

Deux arêtes valent parfois mieux qu'une

Sur le graphe ci-dessous, aller de A à B directement coûte 4. Passer par C coûte

2 + 1 = 3

.
Le chemin le plus court en nombre d'arêtes n'est donc pas le plus court en poids. Un BFS répondrait « une arête », ce qui est exact et sans intérêt pour qui cherche le trajet le moins cher.

Graphe non orienté et pondéré6 sommets, 9 arêteschemin mis en évidence

Aller de A à B coûte 4 en direct, 3 en passant par C : le plus court en poids n'est pas le plus court en nombre d'arêtes.

Dijkstra

Principe

On maintient une distance provisoire $\mathrm{dist}(v)$ pour chaque sommet, infinie au départ sauf pour la source, qui vaut 0. À chaque étape, on fige le sommet non figé de plus petite distance provisoire, puis on relâche ses arêtes : pour chaque voisin, si passer par lui fait mieux, on met à jour.

Le relâchement, en une ligne

\text{si } \mathrm{dist}(u) + \mathrm{poids}(u,v) < \mathrm{dist}(v) \text{ alors } \mathrm{dist}(v) \leftarrow \mathrm{dist}(u) + \mathrm{poids}(u,v)

et l'on note au passage $u$ comme prédécesseur de $v$  : c'est lui qui permettra de reconstruire le chemin.

Dérouler la figure ci-dessous : à chaque pas, elle fige le sommet qui porte la plus petite distance provisoire, écrit en clair chaque relâchement, et ajoute une ligne au tableau des distances. Le tas y est dessiné aussi, avec ses entrées périmées, sur lesquelles le code reviendra. Les arêtes en gras forment l'arbre des plus courts chemins.

Dijkstra depuis A6 sommets, 9 arêtes

0 / 6

Algorithme

Cliquer un sommet pour en faire la source, un poids pour le modifier.

Plein : figé, avec son rang. Sous chaque sommet, sa distance provisoire. En gras : l'arbre des plus courts chemins ; en tirets : un prédécesseur encore provisoire.

Tascouples (distance, sommet), le plus petit sort le premier

(0, A)

Tableau de Dijkstra : une ligne par sommet figé ; chaque case donne la distance provisoire et, entre parenthèses, le prédécesseur ; la valeur en gras est celle qu'on fige ; une case vide désigne un sommet déjà figé.
on fige	A	B	C	D	E	F
Aucune ligne encore : dérouler pour figer la source.

Départ : dist(A) = 0, toutes les autres distances valent ∞. Le tas contient (0, A) ; rien n'est encore figé.

Dijkstra depuis A. Les arêtes en gras relient chaque sommet à son prédécesseur : elles forment l'arbre des plus courts chemins.

À manipuler

Dérouler jusqu'au bout, et comparer le tableau de la figure à celui de l'exemple plus bas : ce sont les mêmes lignes. Au deuxième pas, le récit écrit « dist(B) : 4 → 3 par C » : c'est le relâchement qui améliore. Cliquer ensuite le poids de l'arête A-C et le porter à 6 : B est alors figé directement depuis A, à 4, et l'arbre change. Cliquer enfin F pour en faire la source : l'arbre se refait autour de lui.

Les distances finales sont $\mathrm{dist}(A)=0$ , $\mathrm{dist}(C)=2$ , $\mathrm{dist}(B)=3$ , $\mathrm{dist}(D)=8$ , $\mathrm{dist}(E)=10$ , $\mathrm{dist}(F)=13$ . Remarquer $\mathrm{dist}(B)$  : la valeur 4 trouvée au premier tour a été améliorée en 3 quand on est passé par C. C'est tout le sens du relâchement.

Le tableau de Dijkstra, à la main

À la main, on tient un tableau d'une ligne par sommet figé. Chaque case donne la distance provisoire après les relâchements de cette ligne et, entre parenthèses, le prédécesseur qui l'a fournie ; la valeur en gras est celle qu'on fige. Une case laissée vide désigne un sommet déjà figé, qui ne bouge plus.

on fige	A	B	C	D	E	F
A	0	4 (A)	2 (A)	$\infty$	$\infty$	$\infty$
C		3 (C)	2 (A)	10 (C)	12 (C)	$\infty$
B		3 (C)		8 (B)	12 (C)	$\infty$
D				8 (B)	10 (D)	14 (D)
E					10 (D)	13 (E)
F						13 (E)

Pour obtenir le chemin de A à F, on remonte les prédécesseurs : F vient de E, E de D, D de B, B de C, C de A. Le chemin est A, C, B, D, E, F, de poids 13.

Pourquoi figer le plus petit est correct. Dijkstra est un algorithme glouton, au sens du chapitre précédent : à chaque étape, il fait le choix qui paraît le meilleur, figer le sommet le plus proche, et ne revient jamais sur un sommet figé. Ce glouton-là est exact, à une condition.
Quand on choisit le sommet non figé de plus petite distance provisoire, aucun chemin ne pourra faire mieux ensuite : tout autre trajet passerait par un sommet non figé, donc de distance déjà supérieure, et ne ferait qu'ajouter du poids.
Cet argument suppose que les poids sont positifs. C'est exactement là que tout se joue.

Ce qui casse avec un poids négatif

Dijkstra depuis A4 sommets, 4 arcs

0 / 4

Algorithme

Cliquer un sommet pour en faire la source, un poids pour le modifier.

Plein : figé, avec son rang. Sous chaque sommet, sa distance provisoire. En gras : l'arbre des plus courts chemins ; en tirets : un prédécesseur encore provisoire.

Tascouples (distance, sommet), le plus petit sort le premier

(0, A)

Tableau de Dijkstra : une ligne par sommet figé ; chaque case donne la distance provisoire et, entre parenthèses, le prédécesseur ; la valeur en gras est celle qu'on fige ; une case vide désigne un sommet déjà figé.
on fige	A	B	C	D
Aucune ligne encore : dérouler pour figer la source.

Départ : dist(A) = 0, toutes les autres distances valent ∞. Le tas contient (0, A) ; rien n'est encore figé.

Un poids est négatif : Dijkstra n'est plus garanti. Le dérouler jusqu'au bout, et la figure comparera sa réponse à celle de Bellman-Ford.

Quatre arcs suffisent à mettre Dijkstra en défaut. Le chemin A, C, B, D coûte 2, alors que Dijkstra a déjà figé D à 3.

À manipuler

Dérouler Dijkstra pas à pas. Au quatrième pas, il fige C, et le récit dit ce que l'arc C → B aurait donné si B n'avait pas été figé. Une fois au bout, la figure compare sa réponse à celle de Bellman-Ford et désigne le premier sommet faux. Porter ensuite le poids de C → B à −2 : Dijkstra tombe juste, par chance, et rien dans sa réponse ne le distingue du cas précédent. Basculer enfin sur Bellman-Ford : il trouve les bonnes distances en trois passes et un contrôle, celles du tableau de la section suivante.

Dijkstra fige A, puis B à la distance 2, parce que 2 est la plus petite valeur provisoire, puis D à $2 + 1 = 3$ . Il fige enfin C à 5, relâche l'arc C -> B et découvre $5 - 4 = 1$ , meilleur que 2. Mais B est déjà figé, et D aussi, calculé à partir de lui : l'algorithme ne revient pas en arrière. Il annonce 2 pour B et 3 pour D, alors que les vraies distances sont 1, par A, C, B, et 2, par A, C, B, D. La réponse est fausse.

Une implémentation qui oublierait de protéger les sommets figés corrigerait ici $\mathrm{dist}(B)$ après coup, mais pas ce qui a déjà été calculé à partir de B : elle annoncerait toujours 3 pour D, et ses résultats ne seraient même plus cohérents entre eux. C'est pourquoi le code plus bas ne relâche jamais un arc vers un sommet figé.

L'hypothèse n'est pas une formalité

Un poids négatif détruit l'argument qui justifie de figer : ajouter une arête peut désormais diminuer le coût, donc un sommet lointain peut offrir un raccourci.
Dijkstra sur des poids négatifs ne plante pas, ne signale rien, et peut rendre un résultat faux, ou juste par chance sur l'exemple qu'on a essayé : avec les arcs A → B de poids

-1

, A → C de poids 3 et B → C de poids 1, il trouve les bonnes distances. C'est la pire des situations, et c'est pourquoi la question « les poids sont-ils tous positifs ? » doit être posée avant d'écrire la moindre ligne.

Vérification rapideon peut se reprendre

Dijkstra sur un graphe contenant un arc de poids négatif…

Et si un circuit a un poids total négatif, la question elle-même perd son sens : on peut le parcourir indéfiniment pour faire baisser le coût, et il n'existe pas de plus court chemin.

Graphe orienté et pondéré5 sommets, 5 arcschemin mis en évidence

Le circuit X, Y, Z pèse 3 − 2 − 2 = −1. Chaque tour retire 1 au coût de tout chemin qui l'emprunte, et rien n'oblige à s'arrêter.

Poids négatif et circuit négatif ne sont pas la même chose

Un arc de poids négatif est parfaitement admissible : Bellman-Ford le traite sans difficulté, et il modélise très bien un gain, une remise, un remboursement.
Ce qui rend le problème insoluble, c'est un circuit dont la somme des poids est négative, et lui seul. La distance de

S

T

n'est alors pas « très petite » : elle n'existe pas, puisqu'aucun minimum n'est atteint.
Un circuit négatif n'empoisonne d'ailleurs pas tout le graphe : seuls les sommets qu'il peut atteindre perdent leur distance. Un sommet situé en amont, ou dans une autre composante, garde la sienne.

Ce qu'un circuit négatif veut dire hors des mathématiques

Sur un graphe de conversions de devises où le poids d'un arc est

-\ln(\text{taux})

, un circuit de poids négatif est exactement une séquence de changes qui rapporte de l'argent en revenant à la devise de départ. Détecter un tel circuit, c'est détecter une opportunité d'arbitrage, et c'est l'un des usages réels de Bellman-Ford.

Bellman-Ford

Principe

Relâcher toutes les arêtes, $n - 1$ fois de suite. Un plus court chemin ayant au plus $n - 1$ arêtes, cela suffit pour que toutes les distances soient correctes.

Une passe supplémentaire qui améliore encore une distance prouve l'existence d'un circuit de poids négatif.

Bellman-Ford est plus lent que Dijkstra, en $O(n \times m)$ contre $O(m \log n)$ , mais il accepte les poids négatifs et sait dire quand le problème n'a pas de solution.

Une exécution complète, passe par passe

Sur le graphe du contre-exemple, depuis la source $A$ , avec les arcs relâchés dans l'ordre $B \to D$ , puis $C \to B$ , puis $A \to C$ , puis $A \to B$ . Cet ordre est volontairement le plus défavorable. Avec $n = 4$ sommets, il faut au plus $n - 1 = 3$ passes, plus une de contrôle.

après	$\mathrm{dist}(A)$	$\mathrm{dist}(B)$	$\mathrm{dist}(C)$	$\mathrm{dist}(D)$	ce qui s'est passé
initialisation	$0$	$\infty$	$\infty$	$\infty$
passe 1	$0$	$2$	$5$	$\infty$	$B \to D$ et $C \to B$ ne servent à rien, $B$ et $C$ sont encore à $\infty$
passe 2	$0$	$\mathbf{1}$	$5$	$3$	$B \to D$ donne $2 + 1 = 3$  ; $C \to B$ trouve enfin $5 - 4 = 1$
passe 3	$0$	$1$	$5$	$\mathbf{2}$	$B \to D$ repart de la nouvelle valeur de $B$  : $1 + 1 = 2$
passe 4 (contrôle)	$0$	$1$	$5$	$2$	rien ne bouge : les distances sont définitives

Deux enseignements. D'abord, l'arc $C \to B$ n'a servi qu'à la deuxième passe, parce qu'à la première $\mathrm{dist}(C)$ était encore infinie, et la bonne valeur de $D$ n'arrive qu'à la troisième, parce qu'elle attend celle de $B$  : chaque passe propage l'information d'un arc de plus le long des chemins. C'est exactement la raison d'être des passes répétées, et c'est pourquoi l'algorithme ne cherche pas à ordonner les arcs intelligemment. Il n'en a pas besoin.

Ensuite, la quatrième passe ne change rien, et c'est elle qui prouve l'absence de circuit négatif. Elle n'est pas facultative : c'est le contrôle, et il ne coûte qu'un parcours de plus des $m$ arcs.

Pourquoi $n - 1$ passes suffisent. Un plus court chemin ne repasse jamais par un sommet, sinon il contiendrait un circuit de poids positif ou nul qu'on pourrait retirer. Il a donc au plus $n - 1$ arcs.
Or chaque passe garantit que tous les plus courts chemins d'un arc de plus sont désormais corrects : après la passe $k$ , toutes les distances atteintes en au plus $k$ arcs sont exactes. Il suffit donc de $n - 1$ passes dans le pire des cas, et souvent de moins.
Et si une $n$ -ième passe améliore encore quelque chose, c'est qu'un chemin de $n$ arcs bat tous ceux de $n - 1$  : il repasse forcément par un sommet, donc il contient un circuit, et ce circuit est nécessairement de poids négatif.

La figure suivante reprend le graphe au circuit négatif et y déroule Bellman-Ford, une passe par pas, dans la forme du tableau précédent.

Bellman-Ford depuis S5 sommets, 5 arcs

0 / 5

Algorithme

Cliquer un sommet pour en faire la source, un poids pour le modifier.

Ce graphe a un circuit : aucune disposition en couches ne fait aller tous les arcs dans le même sens, et un arc revient en arrière.

Sous chaque sommet, sa distance après la passe ; cerclé : modifiée pendant cette passe. Trait épais : un arc qui vient de faire baisser une distance ; en tirets : les prédécesseurs, qui ne forment l'arbre des plus courts chemins, en gras, qu'à la fin.

Ordre des arcs à chaque passe : S → X, X → Y, Y → Z, Z → X, Z → T

Tableau de Bellman-Ford : une ligne par passe ; chaque case donne la distance et, entre parenthèses, le prédécesseur ; en gras, une valeur modifiée pendant la passe.
après	S	X	Y	Z	T
initialisation	0	∞	∞	∞	∞

Initialisation : dist(S) = 0, toutes les autres distances valent ∞. Chaque passe relâche tous les arcs, dans l'ordre indiqué ; au plus 4 passes, puis une de contrôle.

Bellman-Ford depuis S, sur le graphe au circuit X, Y, Z de poids −1 : la passe de contrôle fait encore baisser une distance.

À manipuler

Dérouler les quatre passes : à partir de la deuxième, X, Y, Z et T baissent de 1 à chaque passe, parce que chacune fait faire au circuit un tour de plus. La cinquième, celle de contrôle, les fait encore baisser : la figure remonte les prédécesseurs, trouve le circuit X → Y → Z → X, de poids −1, et dit quels sommets n'ont pas de plus court chemin. Porter ensuite le poids de X → Y à 4 : le circuit pèse 0, et la deuxième passe ne change déjà plus rien. Basculer enfin sur Dijkstra : il annonce des nombres, sans rien signaler.

Voici les deux algorithmes en Python. Dijkstra range ses distances provisoires dans la file de priorité du chapitre précédent : le tas heapq lui rend à chaque tour le sommet non figé de plus petite distance provisoire, celui qu'il faut figer.

main.py

Sortie

>_ Prêt à exécuter…

main.py

Sortie

>_ Prêt à exécuter…

L'entrée périmée dans le tas

L'implémentation ci-dessus n'enlève jamais rien du tas : quand une distance s'améliore, elle y ajoute simplement une nouvelle entrée. Les anciennes deviennent périmées et sont ignorées grâce au test if u in fige.
C'est plus simple et plus rapide que de chercher puis modifier l'entrée existante, au prix d'un tas légèrement plus gros. C'est l'implémentation standard en Python, où heapq n'offre pas de diminution de clé.

Vérification rapideon peut se reprendre

1.Des chemins mènent de la source à la cible, et pourtant aucun n'est le plus court. Pourquoi ?

2.Toutes les arêtes valent 1. Que vaut-il mieux utiliser ?

Quel algorithme pour quel problème

Situation	Algorithme	Coût
Toutes les arêtes de même poids	BFS	$\Theta(n + m)$
Poids positifs, une source	Dijkstra	$O(m \log n)$
Poids négatifs possibles, une source	Bellman-Ford	$O(n \times m)$
Toutes les paires de sommets	Floyd-Warshall	$\Theta(n^3)$
Poids positifs, cible connue, estimation disponible	A*	dépend de l'heuristique
Graphe orienté sans circuit, poids quelconques	relâchement dans l'ordre topologique (chapitre suivant)	$\Theta(n + m)$

Floyd-Warshall calcule d'un coup les distances entre toutes les paires de sommets, en essayant chaque sommet comme étape intermédiaire. A* est un Dijkstra guidé vers une cible par une estimation de la distance restante, décrit dans les exercices type plus bas. Sur un graphe orienté sans circuit enfin, relâcher chaque arc une seule fois, dans l'ordre du tri topologique du chapitre suivant, donne toutes les distances, même avec des poids négatifs.

Prim et Dijkstra, encore

Les deux algorithmes ont la même forme : un tas, un ensemble qui grossit, une comparaison. Une seule expression change.
Prim compare le poids de l'arête : poids(u, v).
Dijkstra compare la distance cumulée depuis la source : dist(u) + poids(u, v).
Se tromper d'expression donne un programme qui tourne, ne signale rien, et répond à l'autre question.

Mettre en pratique

Pourquoi Dijkstra peut-il se tromper sur un poids négatif ?

Parce que sa correction repose sur un argument précis : quand on fige le sommet de plus petite distance provisoire, aucun chemin ultérieur ne peut faire mieux, puisque tout autre trajet passerait par un sommet de distance déjà supérieure et ne ferait qu'ajouter du poids.

Avec un poids négatif, ajouter une arête peut diminuer le coût. L'argument tombe, et un sommet figé trop tôt garde une valeur fausse.

Le pire est que l'algorithme ne le signale pas : il peut rendre un résultat plausible et faux, et le même code, essayé sur un autre graphe à arc négatif, peut tomber juste par chance.

Des chemins existent de la source à la cible, mais aucun n'est le plus court. Que se passe-t-il ?

Il existe un circuit de poids négatif accessible depuis la source et menant à la cible.

En tournant sur ce circuit, on fait baisser le coût autant qu'on veut : il n'existe pas de minimum, donc pas de plus court chemin.

C'est précisément ce que détecte la passe supplémentaire de Bellman-Ford : si une distance s'améliore encore après $n - 1$ passes, un tel circuit existe.

Combien de passes fait Bellman-Ford, et pourquoi ce nombre ?

$n - 1$ passes, chacune relâchant toutes les arêtes.

Un plus court chemin élémentaire ne peut pas contenir plus de $n - 1$ arêtes, puisqu'il ne répète aucun sommet. Après $k$ passes, toutes les distances atteignables par un chemin d'au plus $k$ arêtes sont correctes.

En pratique on s'arrête dès qu'une passe ne change plus rien, ce qui arrive souvent bien avant.

Comment obtenir le chemin et pas seulement son poids ?

En mémorisant, pour chaque sommet, le prédécesseur qui a permis la dernière amélioration de sa distance.

À la fin, on part de la cible et on remonte de prédécesseur en prédécesseur jusqu'à la source, puis on retourne la liste obtenue.

Ce tableau ne coûte rien en temps ni en mémoire significative, et c'est exactement le même mécanisme que pour le BFS.

Quand utiliser A\* plutôt que Dijkstra ?

Quand on cherche le chemin vers une cible précise et qu'on dispose d'une estimation de la distance restante, par exemple la distance à vol d'oiseau sur une carte.

Dijkstra explore dans toutes les directions à la fois. A* oriente l'exploration vers la cible en ajoutant cette estimation à la priorité, ce qui réduit beaucoup le nombre de sommets visités.

La condition à respecter : l'estimation ne doit jamais surestimer la distance restante, sans quoi A* peut renvoyer un chemin non optimal. Et pour ne jamais revenir sur un sommet déjà traité, comme le fait Dijkstra, elle ne doit pas non plus baisser de plus que le poids de l'arc parcouru. La distance à vol d'oiseau remplit les deux conditions.

Sur un graphe où toutes les arêtes valent 1, faut-il Dijkstra ?

Non, un simple BFS suffit et il est plus rapide.

Avec des poids identiques, l'ordre de traitement par distance croissante est exactement l'ordre de découverte du BFS : la file de priorité n'apporte rien et coûte un facteur logarithmique.

C'est un réflexe utile : avant de sortir Dijkstra, vérifier si les poids sont vraiment différents.

Deux notions de « plus court »

Dijkstra

Ce qui casse avec un poids négatif

Bellman-Ford

Quel algorithme pour quel problème

Mettre en pratique

Dans la bibliothèque d'exercices

Deux notions de « plus court »