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. Un plus court chemin de $u$ à $v$ est un chemin de $u$ à $v$ de poids minimal.

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

Dijkstra

Principe

On maintient une distance provisoire pour chaque sommet, infinie au départ sauf pour la source. À 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 } d(u) + poids(u,v) < d(v) \text{ alors } d(v) \leftarrow d(u) + poids(u,v)

Dérouler : le sommet figé à chaque étape est celui qui portait la plus petite distance provisoire. Les arêtes en gras forment l'arbre des plus courts chemins.

Graphe non orienté et pondéré6 sommets, 9 arêtes

0 / 6

Rien n'est encore visité.

Les distances finales sont $d(A)=0$ , $d(C)=2$ , $d(B)=3$ , $d(D)=8$ , $d(E)=10$ , $d(F)=13$ . Remarquer d(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.

Pourquoi figer le plus petit est correct

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

Graphe orienté et pondéré3 sommets, 3 arêtes

Trois arcs suffisent à mettre Dijkstra en défaut. Le chemin A, C, B coûte 1, alors que l'arc direct coûte 2.

Dijkstra fige B à la distance 2, parce que 2 est la plus petite valeur provisoire. Puis il fige C à 5, relâche l'arc C -> B et découvre $5 - 4 = 1$ , meilleur que 2. Mais B est déjà figé : l'algorithme ne revient pas en arrière, et il renvoie une réponse fausse.

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 rend un résultat faux. 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.

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 arêteschemin 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.

Vérification rapideon peut se reprendre

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

2.Que signifie l'absence de plus court chemin dans un graphe ?

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

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 petit graphe du contre-exemple, depuis la source $A$ , avec les arcs relâchés dans l'ordre $C \to B$ , puis $A \to C$ , puis $A \to B$ . Cet ordre est volontairement le plus défavorable.

après	$d(A)$	$d(B)$	$d(C)$	ce qui s'est passé
initialisation	$0$	$\infty$	$\infty$
passe 1	$0$	$2$	$5$	$C \to B$ ne sert à rien, $d(C)$ vaut encore $\infty$
passe 2	$0$	$\mathbf{1}$	$5$	$C \to B$ trouve enfin $5 - 4 = 1$
passe 3 (contrôle)	$0$	$1$	$5$	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 $d(C)$ était encore infinie : 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 troisiè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 exactement

n - 1

passes

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, ni plus, ni 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.

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é.

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

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 : d(u) + poids(u, v).
Se tromper d'expression donne un programme qui tourne, ne signale rien, et répond à l'autre question.

Exercices type

Pourquoi Dijkstra échoue-t-il 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 rend un résultat plausible et faux.

Que signifie l'absence de plus court chemin dans un graphe ?

Qu'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 sa longueur ?

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. Sinon A* peut renvoyer un chemin non optimal.

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.

La méthode

Regarder les poids d'abord : identiques, positifs, ou possiblement négatifs.
BFS si tout vaut 1, Dijkstra si tout est positif, Bellman-Ford sinon.
Écrire le relâchement avant le reste : c'est la ligne qui porte l'algorithme.
Mémoriser le parent dès le départ, pas après coup.
Ignore les entrées périmées du tas au lieu de chercher à les modifier.
Vérifier la présence d'un circuit négatif avant d'annoncer un résultat.
Relire l'expression comparée : poids de l'arête pour Prim, distance cumulée pour Dijkstra.

Synthèse

Le plus court chemin en poids n'est pas le plus court en nombre d'arêtes.
Dijkstra fige à chaque étape le sommet de plus petite distance provisoire.
Le relâchement est la seule opération de l'algorithme.
Dijkstra exige des poids positifs ; sinon il rend une réponse fausse en silence.
Un circuit de poids négatif supprime l'existence même d'un plus court chemin.
Bellman-Ford fait $n - 1$ passes et détecte ces circuits.
Le tableau des prédécesseurs reconstruit le chemin.
Prim compare le poids d'une arête, Dijkstra une distance cumulée.
Si tous les poids valent 1, le BFS suffit.

Deux notions de « plus court »