Plus courts chemins

Où on va

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éroulez : 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$ . Remarquez 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

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.

Vérification rapidesans note, on 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.

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érifiez si les poids sont vraiment différents.

La méthode

Regarde les poids d'abord : identiques, positifs, ou possiblement négatifs.
BFS si tout vaut 1, Dijkstra si tout est positif, Bellman-Ford sinon.
Écris le relâchement avant le reste : c'est la ligne qui porte l'algorithme.
Mémorise 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érifie la présence d'un circuit négatif avant d'annoncer un résultat.
Relis l'expression comparée : poids de l'arête pour Prim, distance cumulée pour Dijkstra.

En résumé

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.

Et ensuite ? Jusqu'ici les arêtes n'avaient pas de sens de circulation. Le chapitre suivant passe aux graphes orientés, où l'absence de circuit ouvre des possibilités que les graphes non orientés n'ont pas.

Ce que ce chapitre apporte

Deux notions de « plus court »