Plus courts chemins

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• énoncer les quatre formes du problème du plus court chemin — une paire, une source, une destination, toutes les paires — et expliquer pourquoi la première n'est pas plus facile que la deuxième;
• écrire la relaxation d'une arête, la reconnaître comme l'unique opération dont tous les algorithmes de ce chapitre sont faits, et démontrer l'invariant $d[v]\ge \delta (s,v)$ qu'elle préserve;
• dérouler l'algorithme de Dijkstra à la main sur un graphe donné, en écrivant la file de priorité et l'ensemble des sommets figés à chaque étape, et démontrer sa correction par l'invariant sur l'ensemble extrait;
• dire où exactement cette démonstration échoue lorsqu'une arête porte un poids négatif, et construire un contre-exemple à quatre sommets;
• implémenter Bellman–Ford, justifier ses $n-1$ passes, détecter un circuit de poids négatif à la $n$-ième, et traiter un graphe sans circuit en $O(n+m)$ par tri topologique;
• remplir la table de Floyd–Warshall, dire ce que représente l'indice du sommet intermédiaire, et choisir entre ces algorithmes selon la densité du graphe et le signe des poids.

Le problème, et ses quatre formes

Le chapitre 6 a introduit le graphe témoin du cours et son vocabulaire: sommets, arêtes, listes d'adjacence, parcours en largeur et en profondeur. Le parcours en largeur y répondait déjà à une question de plus court chemin — celle où toutes les arêtes se valent, et où «le plus court» veut dire «le moins d'arêtes». Ce chapitre reprend la même question quand les arêtes ne se valent pas: chacune porte un poids, et le coût d'un trajet est la somme des poids qu'il traverse.

Le mot «poids» est volontairement neutre. Selon l'application ce sera une distance en kilomètres, une durée en minutes, un tarif en francs, une probabilité transformée en son logarithme changé de signe, un taux de perte sur une liaison réseau. Les algorithmes de ce chapitre ne savent rien de tout cela; ils savent additionner des poids et les comparer. C'est précisément cette indifférence qui fait qu'un même algorithme calcule l'itinéraire d'un train, la route d'un paquet IP et la séquence d'opérations la moins chère dans un compilateur.

Les deux conventions ne sont pas des coquetteries. La première est celle qui permet d'écrire un algorithme uniforme: on initialise toutes les estimations à $+\infty$ et l'absence de chemin se lit dans le résultat. La seconde dit une chose plus profonde. Si un circuit de poids $-3$ est accessible depuis $s$ et permet ensuite d'atteindre $v$, alors en le parcourant deux fois, dix fois, mille fois, on fabrique des trajets de poids arbitrairement bas: il n'y a pas de minimum, et parler du plus court chemin n'a plus de sens. Nous y reviendrons en détail, parce que c'est exactement ce que Bellman–Ford sait détecter.

Quatre problèmes, pas un

Ce que l'on demande n'est pas toujours la même chose, et l'usage distingue quatre formulations.

Une paire (single pair): on donne $s$ et $t$, on veut $\delta (s,t)$ et un chemin qui la réalise. C'est la forme que vous utilisez quand vous demandez un itinéraire.

Une source (single source): on donne $s$, on veut $\delta (s,v)$ pour tout sommet $v$. C'est la forme que résolvent Dijkstra et Bellman–Ford.

Une destination (single destination): on donne $t$, on veut $\delta (v,t)$ pour tout $v$. Dans un graphe orienté, il suffit d'inverser le sens de tous les arcs et de résoudre le problème à source unique depuis $t$ sur ce graphe transposé; dans un graphe non orienté, les deux problèmes sont le même, puisque $\delta (u,v)=\delta (v,u)$.

Toutes les paires (all pairs): on veut $\delta (u,v)$ pour tous les couples. C'est ce que calcule Floyd–Warshall, et ce que l'on obtient aussi en lançant $n$ fois un algorithme à source unique.

Reste la question qui surprend toujours: pourquoi ne pas traiter «une paire» plus efficacement que «une source»? On calcule apparemment $n$ fois plus de choses dans le second cas.

La réponse tient en une observation et un constat honnête. L'observation, c'est qu'on ne sait pas décider que l'on a trouvé $\delta (s,t)$ sans avoir prouvé que tous les autres trajets sont plus longs. Un algorithme qui s'arrête en annonçant la valeur 17 doit garantir qu'aucun détour n'aurait fait mieux, et pour cela il lui faut avoir exploré suffisamment le graphe. Dijkstra, par exemple, peut s'arrêter dès qu'il extrait $t$ — mais dans le pire des cas $t$ est le dernier sommet extrait, et l'algorithme a alors calculé la distance à tous les sommets sans le vouloir. Le constat, c'est qu'aucun algorithme connu ne résout la forme «une paire» avec une meilleure complexité asymptotique dans le pire des cas que la forme «une source». Ce n'est pas un théorème — personne n'a démontré qu'un tel algorithme ne peut pas exister — mais c'est l'état de l'art, et la pratique s'y conforme: on résout le problème à source unique et on s'arrête plus tôt quand on le peut. L'algorithme A*, en fin de chapitre, est précisément l'art de s'arrêter plus tôt.

La relaxation, seule opération de tout le chapitre

Tous les algorithmes qui suivent — Dijkstra, Bellman–Ford, le passage par un ordre topologique, et jusqu'à Floyd–Warshall sous une autre écriture — sont faits d'une seule opération, répétée dans des ordres différents. Il vaut donc la peine de l'isoler, de la nommer, et de démontrer une fois pour toutes ce qu'elle garantit.

Chaque algorithme maintient, pour chaque sommet $v$, une estimation $d[v]$ de la distance depuis la source, et un prédécesseur $\mathrm{parent}[v]$ qui mémorise par quelle arête cette estimation a été obtenue. L'initialisation pose $d[s]=0$ et $d[v]=+\infty$ pour les autres.

En Python, c'est une fonction de cinq lignes, et elle renvoie l'information dont Bellman–Ford aura besoin: l'estimation a-t-elle changé?

def relacher(d, parent, u, v, poids):
    """Ameliore d[v] en passant par u ; renvoie True si l'estimation a change."""
    if d[u] + poids < d[v]:
        d[v] = d[u] + poids
        parent[v] = u
        return True
    return False

L'inégalité est stricte. En cas d'égalité on ne touche à rien, ce qui n'a aucune conséquence sur les distances calculées — elles seraient les mêmes — mais en a une sur l'arbre des prédécesseurs: à égalité, le premier chemin trouvé est conservé. C'est ce qui rend les traces de ce chapitre reproductibles, et c'est aussi ce qui explique que deux implémentations correctes puissent renvoyer deux arbres différents avec les mêmes distances.

Ce que la relaxation garantit

Trois énoncés suffisent à démontrer la correction de tout ce chapitre. Le premier dit qu'une estimation ne descend jamais sous la vérité; le deuxième, qu'un morceau de plus court chemin est un plus court chemin; le troisième, qu'une relaxation faite au bon moment fige définitivement la bonne valeur.

Démonstration. Point 1. Si $\delta (s,u)=+\infty$, l'inégalité est vraie trivialement. Si $\delta (s,u)=-\infty$, alors $\delta (s,v)=-\infty$ aussi, puisque le circuit négatif qui rend $u$ inaccessible par en dessous permet ensuite d'atteindre $v$ par l'arête , et l'inégalité est encore vraie. Sinon, prenons un chemin de à de poids ; le chemin obtenu en lui ajoutant l'arête va de à et pèse . Comme est le plus petit poids d'un tel trajet, .

Point 2. Par récurrence sur le nombre de relaxations déjà effectuées. À l'initialisation, $d[s]=0\ge \delta (s,s)$ — car $\delta (s,s)\le 0$, le chemin vide étant de poids nul — et $d[v]=+\infty \ge \delta (s,v)$ pour les autres. Supposons la propriété vraie avant une relaxation de . Si elle échoue, rien ne change. Si elle réussit, la nouvelle valeur est , et par hypothèse de récurrence , donc

la dernière inégalité étant le point 1. La propriété est donc préservée. Pour la seconde affirmation: une estimation finie a été posée par une relaxation, à partir d'une estimation finie de $u$; en remontant la chaîne des prédécesseurs jusqu'à $s$, on exhibe un chemin de ce poids exactement.

Point 3. La règle (7.2) ne modifie $d[v]$ que par une valeur strictement plus petite. La suite des valeurs prises par $d[v]$ est donc strictement décroissante, et le point 2 la minore par $\delta (s,v)$: une fois atteinte, cette borne ne peut plus être franchie ni quittée. $\square$

Le point 2 est l'invariant central du chapitre. Il dit qu'aucun algorithme fait de relaxations ne peut mentir en annonçant une distance trop petite. Toute la difficulté restante est donc de garantir l'autre sens: que $d[v]$ finisse par descendre jusqu'à $\delta (s,v)$. C'est là que les algorithmes se distinguent, et c'est là seulement.

Démonstration. Découpons $p$ en trois morceaux consécutifs: $p_{0i}$ de $v_0$ à $v_i$, puis $p_{ij}$, puis . Les poids s'additionnent, donc

Supposons qu'il existe un chemin $p_{ij}^{\prime }$ de $v_i$ à $v_j$ avec $w(p_{ij}^{\prime })<w(p_{ij})$. En le substituant au milieu, on obtient un trajet de à — la concaténation est licite, puisque les extrémités coïncident — de poids . Cela contredit le fait que soit de poids minimal. Donc aucun tel n'existe.

Cet argument s'appelle le découper-recoller (cut and paste), et vous le retrouverez au chapitre 10 comme le test d'entrée de la programmation dynamique. Il mérite qu'on note ce qu'il n'affirme pas: il ne dit rien du plus long chemin. Si $p$ est un plus long chemin élémentaire de $v_0$ à $v_k$, son sous-chemin n'est en général pas un plus long chemin élémentaire entre ses extrémités — l'allonger localement peut repasser par un sommet déjà utilisé, et la concaténation cesse d'être un chemin élémentaire. C'est exactement pour cela que le problème du plus long chemin n'a pas de sous-structure optimale, et se trouve du mauvais côté de la frontière que tracera le chapitre 11.

Une conséquence immédiate, qui justifie le mot «chemin élémentaire» du début: s'il n'y a pas de circuit de poids négatif accessible, on peut toujours choisir un plus court chemin élémentaire. En effet, si un plus court chemin repasse par un sommet, il contient un circuit; ce circuit a un poids $\ge 0$, donc le supprimer ne fait pas augmenter le poids total. En répétant l'opération, on aboutit à un chemin élémentaire de poids au plus égal. Il a donc au plus $n-1$ arêtes — retenez ce nombre, c'est lui qui donnera à Bellman–Ford son nombre de passes.

Démonstration. Par le théorème 7.2 appliqué au chemin $⟨s,\dots ,u,v⟩$, son préfixe $⟨s,\dots ,u⟩$ est un plus court chemin de $s$ à $u$, d'où $\delta (s,v)=\delta (s,u)+w(u,v)$. Après la relaxation de , la règle (7.2) garantit

que la relaxation ait réussi ou non — si elle a échoué, c'est que $d[v]$ était déjà inférieur ou égal à cette quantité. Le point 2 du théorème 7.1 donne l'inégalité inverse $d[v]\ge \delta (s,v)$, d'où l'égalité. Le point 3 du même théorème interdit ensuite toute modification. $\square$

Ce théorème est le moule de toutes les démonstrations de correction qui suivent. Chacune consistera à établir que l'algorithme relâche les arêtes dans un ordre tel que, pour chaque sommet $v$, la dernière arête d'un plus court chemin vers $v$ est relâchée à un moment où l'estimation de son origine est déjà juste. Dijkstra l'obtient par l'ordre de la file de priorité; Bellman–Ford, par la force brute des passes répétées; l'algorithme sur graphe sans circuit, par l'ordre topologique.

L'algorithme de Dijkstra

Edsger Dijkstra a publié cet algorithme en 1959, dans un article de trois pages qui en contenait deux. L'idée est d'une simplicité qui fait un peu peur: si tous les poids sont positifs ou nuls, le sommet non encore figé dont l'estimation est la plus petite a déjà la bonne valeur. On peut donc le figer, relâcher ses arêtes, et recommencer.

L'algorithme

L'algorithme maintient deux ensembles: les sommets figés (dont on affirme que $d[v]=\delta (s,v)$) et les autres, rangés dans une file de priorité ordonnée par estimation croissante. À chaque tour il extrait le minimum, le fige, et relâche toutes ses arêtes sortantes.

import heapq

def dijkstra(graphe, source):
    """Renvoie les distances, les predecesseurs et l'ordre d'extraction."""
    d = {s: float("inf") for s in graphe}
    d[source] = 0
    parent, ordre, figes = {}, [], set()
    tas = [(0, source)]
    while tas:
        du, u = heapq.heappop(tas)
        if u in figes:                       # entree perimee : on l'ignore

Trois détails d'implémentation méritent un mot, car ils reviennent dans toutes les bibliothèques.

Le tas de heapq est un tas-min binaire, celui du chapitre 5: heappush et heappop coûtent $O(\log k)$ sur un tas de $k$ éléments. Python n'offrant pas d'opération «diminuer la clé», on ne modifie pas l'entrée existante d'un sommet dont l'estimation baisse: on en pousse une nouvelle, et l'ancienne devient périmée. Le test if u in figes: continue est ce qui les élimine à la sortie. Le tas contient donc jusqu'à $m+1$ entrées au lieu de $n$, ce qui ne change pas la classe de complexité puisque $\log m\le \log n^2=2\log n$.

Le test v not in figes est, lui, la clause dont dépend toute la correction — et c'est aussi elle qui rendra l'algorithme faux avec un poids négatif. Un sommet figé ne sera plus jamais relâché, quoi qu'il arrive ensuite.

Enfin, ordre n'est pas nécessaire à l'algorithme: nous le renvoyons parce que l'ordre d'extraction est exactement ce que le lecteur doit savoir reproduire à la main.

Sur le graphe témoin

La correction de Dijkstra

Nous pouvons maintenant démontrer que l'algorithme dit vrai. La démonstration est courte, et chacun de ses pas mérite d'être lu deux fois, parce que l'un d'eux — un seul — utilise la positivité des poids.

Démonstration. Notons $S$ l'ensemble des sommets déjà figés, qui grandit d'un élément à chaque tour. Raisonnons par l'absurde et supposons que l'énoncé soit faux. Soit alors $u$ le premier sommet extrait tel que $d[u]\ne \delta (s,u)$ au moment de son extraction; par le théorème 7.1, point 2, cela signifie $d[u]>\delta (s,u)$.

Premier point: $u\ne s$. Le sommet $s$ est extrait en premier, avec $d[s]=0$; comme tous les poids sont positifs ou nuls, aucun circuit n'est de poids négatif, donc $\delta (s,s)=0=d[s]$.

Deuxième point: il existe un plus court chemin de $s$ à $u$. Comme $d[u]>\delta (s,u)$ et que $d[u]\le +\infty$, on a $\delta (s,u)<+\infty$, donc $u$ est accessible. Et puisque les poids sont positifs ou nuls. Fixons donc un plus court chemin élémentaire de à .

Troisième point: la coupure. Au moment de l'extraction de $u$, le chemin $p$ part de $s\in S$ et arrive en $u\notin S$. Il traverse donc au moins une fois la frontière de $S$. Soit $y$ le premier sommet de $p$ qui n'est pas dans $S$, et soit son prédécesseur immédiat sur ; par construction , et l'arête appartient à .

Quatrième point: $d[y]=\delta (s,y)$. Le sommet $x$ a été figé avant $u$. Comme $u$ est le premier sommet fautif, $x$ ne l'était pas: $d[x]=\delta (s,x)$ au moment où $x$ a été extrait, et cette valeur n'a plus bougé (théorème 7.1, point 3). Or, juste après avoir figé , l'algorithme a relâché toutes ses arêtes, dont — et n'était pas figé, ni à cet instant ni maintenant, donc la clause ne l'a pas écartée. Le théorème 7.2 dit que le préfixe de qui s'arrête en est un plus court chemin de à , dont la dernière arête est ; le théorème 7.3 s'applique alors et donne , définitivement.

Cinquième point: la comparaison. Le sommet $y$ est situé sur $p$ avant $u$ (ou est $u$ lui-même). Le morceau de $p$ allant de $y$ à $u$ a pour poids $\delta (s,u)-\delta (s,y)$, d'après le théorème 7.2. , donc

Conclusion. En rassemblant: $d[y]=\delta (s,y)\le \delta (s,u)<d[u]$. Mais $y$ n'est pas figé au moment où l'algorithme extrait $u$, et l'algorithme extrait le sommet non figé d'estimation minimale; il aurait donc dû extraire $y$ plutôt que $u$, ou en tout cas on a . Les deux inégalités et sont contradictoires. (Si , la chaîne donne directement , ce qui contredit le choix de .)

Aucun sommet fautif n'existe donc, ce qui démontre l'énoncé. La conclusion finale s'ensuit: chaque sommet accessible est extrait une fois, avec la bonne valeur, et un sommet inaccessible garde $d[v]=+\infty =\delta (s,v)$. $\square$

Le coût

Comptons ce que fait l'algorithme, en distinguant ce qui dépend de la structure de file de priorité et ce qui n'en dépend pas.

Ce qui n'en dépend pas: chaque sommet est figé une fois, et chaque arête est examinée une fois par extrémité figée. Sur un graphe non orienté, cela fait $2m$ tests de relaxation; sur un graphe orienté, $m$. Sur le graphe témoin, $2m=22$ tests, dont 10 réussissent — et les dix réussites sont exactement les dix fois où une estimation a changé dans la table de l'exemple 7.1, initialisations comprises.

Ce qui en dépend: $n$ extractions du minimum, et au plus une insertion (ou une diminution de clé) par relaxation réussie.

Avec un tableau, on cherche le minimum en balayant les $n$ cases: $\Theta (n^2)$ au total pour les extractions, plus $\Theta (m)$ pour les relaxations, soit $O(n^2)$ puisque $m\le n^2$. Avec un tas binaire, chaque extraction coûte et chaque relaxation réussie une insertion en , d'où .

Lequel choisir? Le rapport des deux coûts est de l'ordre de $n^2$ contre $m\log n$. Pour un graphe dense, où $m$ est proche de $n^2$, le tableau gagne: $n^2$ contre $n^2\log n$. Pour un graphe , où est de l'ordre de — un réseau routier, où chaque carrefour a quatre ou cinq voisins —, le tas gagne largement. Un ordre de grandeur pour fixer les idées: avec sommets et arêtes, opérations, contre pour la version à tableau, soit un rapport de l'ordre de . C'est la différence entre une requête et une nuit de calcul.

Le tas de Fibonacci atteint la meilleure borne connue pour Dijkstra, $O(n\log n+m)$, en rendant la diminution de clé amortie constante — «amortie», au sens précis du chapitre 1: une garantie de pire des cas portant sur une suite d'opérations, pas une moyenne. Ses constantes cachées sont assez grandes pour qu'en pratique le tas binaire lui soit souvent préféré; c'est un cas d'école où la classe asymptotique ne décide pas seule.

Pourquoi un poids négatif casse tout

Le mot «casse» est à prendre au sens fort: l'algorithme ne tourne pas plus lentement, il ne boucle pas, il ne signale rien. Il rend une réponse fausse, en un temps normal, sans le moindre avertissement. C'est la pire des façons pour un programme d'échouer, et c'est pourquoi cette section existe.

Un contre-exemple minimal

Construisons le plus petit graphe possible qui mette Dijkstra en défaut. Ce graphe n'est pas le graphe témoin: il est orienté, il porte un poids négatif, et ses sommets portent d'autres noms — $P$, $Q$, $R$, $T$ — pour qu'aucune confusion ne soit possible. Ce n'est pas non plus le graphe auxiliaire $H$ des composantes connexes du chapitre 6, qui est non orienté et compte sept sommets: celui-ci n'appartient qu'à cette section. Ses quatre arcs sont

Les vraies distances depuis $P$ sont $\delta (P,P)=0$, $\delta (P,R)=3$, $\delta (P,Q)=1$ — par $P\to R\to Q$, de poids — et . Il n'y a aucun circuit dans ce graphe, donc aucun circuit négatif, et toutes ces valeurs sont finies et parfaitement définies.

Déroulons Dijkstra. Il extrait $P$ à 0 et relâche ses deux arcs: $d[Q]=2$, $d[R]=3$. Le minimum de la file est maintenant $Q$ à 2 — et l'algorithme le fige. Il relâche $Q\to T$ et pose $d[T]=3$. Puis il extrait à 3 et tente de relâcher : la valeur améliorerait , mais est figé, et la clause écarte la mise à jour. L'algorithme s'arrête sur

Deux valeurs sur quatre sont fausses, et l'erreur commise sur $Q$ s'est propagée à $T$ sans que rien ne l'arrête. Quatre sommets, quatre arcs, un seul poids négatif: c'est le minimum.

Où la démonstration a échoué

Il serait facile de s'arrêter ici, avec un exemple et une mise en garde. Ce serait manquer l'essentiel, qui est de savoir pourquoi. Reprenons le raisonnement du théorème 7.4 sur ce graphe, au moment où l'algorithme s'apprête à extraire $u=Q$.

À cet instant, $S=\{P\}$. Le plus court chemin $p$ de $P$ à $Q$ est $P\to R\to Q$. Son premier sommet hors de $S$ est $y=R$, précédé de . Les points un à quatre de la démonstration passent sans encombre: , un plus court chemin existe, la coupure est bien définie, et est bien la valeur correcte, puisque l'arc a été relâché quand a été figé.

Le cinquième point, lui, s'effondre. Il affirmait $\delta (s,y)\le \delta (s,u)$, au motif que le morceau de chemin allant de $y$ à $u$ pèse au moins zéro. Ici ce morceau est l'arc $R\to Q$, de poids $-2$, et l'inégalité (7.4) devient fausse:

Un sommet situé plus tôt sur un plus court chemin est plus loin de la source. C'est cette monotonie perdue qui détruit tout: la file de priorité classe les sommets par estimation croissante, et l'algorithme en déduit que le minimum est définitif. Cette déduction reposait entièrement sur le fait qu'aucun chemin ne peut redescendre. Avec un poids négatif, il le peut.

Une remarque pour finir, parce qu'elle revient souvent. On ne peut pas rendre les poids positifs en ajoutant une constante $c$ à toutes les arêtes. Un chemin de $k$ arêtes voit son poids augmenter de $kc$: les chemins longs sont pénalisés davantage que les courts, et l'ordre entre eux change. Sur le graphe (7.5), ajouter $c=2$ donne à $P\to Q$ le poids 4 et à $P\to R\to Q$ le poids $5+0=5$: le chemin optimal a changé. Il existe bien une transformation qui préserve les plus courts chemins — elle ajoute à chaque arc la quantité pour un bien choisi, et c'est l'idée de l'algorithme de Johnson comme de A* — mais ce n'est pas une constante, et le potentiel se calcule lui-même par Bellman–Ford. Nous y revenons en fin de chapitre.

Bellman–Ford: la force brute, et la détection des circuits négatifs

Puisque l'ordre astucieux de Dijkstra ne survit pas aux poids négatifs, renonçons à être astucieux. L'idée de Bellman–Ford — publiée séparément par Richard Bellman en 1958 et Lester Ford en 1956 — est de relâcher toutes les arêtes, puis de recommencer, autant de fois qu'il le faut. Combien de fois? Nous avons déjà la réponse: un plus court chemin élémentaire a au plus $n-1$ arêtes.

def bellman_ford(sommets, arcs, source):
    """Renvoie (d, passes), ou None s'il existe un circuit negatif accessible."""
    d = {s: float("inf") for s in sommets}
    d[source] = 0
    passes = 0
    for _ in range(len(sommets) - 1):
        passes += 1
        change = False
        for u, v, poids in arcs:

Le coût se lit dans les boucles: $n-1$ passes de $m$ tests de relaxation, soit $O(nm)$ tests, plus une passe finale. Sur un graphe creux avec $m\approx n$, cela fait $O(n^2)$; sur un graphe dense, $O(n^3)$. C'est nettement plus cher que Dijkstra, et c'est le prix des poids négatifs.

La ligne if not change: break est un raffinement classique: si une passe entière ne modifie rien, aucune passe ultérieure ne modifiera quoi que ce soit, puisque les passes sont identiques. Elle ne change pas la borne du pire des cas, mais elle fait souvent terminer l'algorithme en deux ou trois passes.

Démonstration. Point 1, par récurrence sur $k$. Pour $k=0$: le seul chemin sans arête est le chemin vide de $s$ à $s$, de poids 0, et $d[s]=0$ après l'initialisation. Supposons le résultat acquis après $k$ passes et considérons un chemin $q=⟨s,\dots ,u,v⟩$ de à ayant au plus arêtes. Son préfixe jusqu'à a au plus arêtes, donc après passes . Pendant la passe , l'arc est relâché, et comme n'a pu que baisser entre-temps, la règle (7.2) donne après cette relaxation . Le point 3 du théorème 7.1 assure que ne remontera pas d'ici la fin de la passe.

Point 2. En l'absence de circuit négatif accessible, il existe pour tout sommet accessible $v$ un plus court chemin élémentaire, qui a donc au plus $n-1$ arêtes. Le point 1 avec $k=n-1$ donne $d[v]\le \delta (s,v)$, et l'invariant du théorème 7.1 donne l'inégalité inverse. Pour un sommet inaccessible, aucune relaxation ne peut poser une valeur finie, donc $d[v]$ reste .

Point 3, sens direct. Après convergence, $d[v]=\delta (s,v)$ pour tout $v$, et le point 1 du théorème 7.1 donne $\delta (s,v)\le \delta (s,u)+w(u,v)$, c'est-à-dire $d[v]\le d[u]+w(u,v)$ pour tout arc: aucun test n'est strictement satisfait.

Point 3, réciproque. Soit $C=⟨c_0,c_1,\dots ,c_k=c_0⟩$ un circuit accessible avec . Supposons par l'absurde qu'après passes aucune relaxation ne réussisse, c'est-à-dire que pour tout . Comme le circuit est accessible, toutes ces valeurs sont finies. Sommons les inégalités:

Les deux sommes de gauche et la première somme de droite portent sur les mêmes sommets — le circuit revient à son point de départ — donc elles sont égales et se simplifient. Il reste $0\le w(C)$, ce qui contredit $w(C)<0$. Une relaxation réussit donc encore. $\square$

Ce dernier argument est un bijou de concision, et il mérite d'être relu: il ne s'appuie sur aucune propriété de l'algorithme, seulement sur le fait que $d$ satisfasse toutes les inégalités triangulaires. Autrement dit, il n'existe aucune affectation de valeurs finies $d$ qui les satisfasse toutes en présence d'un circuit négatif. La détection n'est pas une astuce d'implémentation: c'est une impossibilité.

Les graphes sans circuit: linéaire

Il existe une classe de graphes où le problème se résout beaucoup plus vite que par Dijkstra, et même avec des poids négatifs: les graphes orientés sans circuit, ou DAG (directed acyclic graph). Ce sont les graphes de dépendances, les ordonnancements de tâches, les réseaux de neurones à propagation avant, les circuits combinatoires.

L'idée tient en une phrase: le chapitre 6 a montré qu'un graphe orienté sans circuit admet un ordre topologique, c'est-à-dire un rangement de ses sommets tel que tout arc aille de gauche à droite. Si l'on traite les sommets dans cet ordre, alors quand on arrive à $u$, tous les chemins menant à $u$ ont déjà été explorés, puisqu'ils passent uniquement par des sommets situés avant lui. Son estimation est donc déjà définitive, et il suffit de relâcher ses arcs sortants.

def plus_courts_chemins_dag(sommets, arcs, source):
    """Sommets deja ranges dans un ordre topologique."""
    sortants = {s: [] for s in sommets}
    for u, v, poids in arcs:
        sortants[u].append((v, poids))
    d = {s: float("inf") for s in sommets}
    d[source] = 0
    for u in sommets:                    # une seule passe, dans l'ordre topologique
        if d[u] == float("inf"

Le coût: le tri topologique se fait en $\Theta (n+m)$ au chapitre 6, la boucle examine chaque arc exactement une fois, donc $\Theta (n+m)$ au total. C'est optimal à une constante près, puisqu'il faut au moins lire le graphe.

La correction s'obtient par le théorème 7.3, en récurrence sur la position dans l'ordre topologique: quand on traite $u$, tous ses prédécesseurs sur un plus court chemin le précèdent dans l'ordre, ont donc déjà été traités, et leurs arcs vers $u$ ont déjà été relâchés au moment où leur propre estimation était juste. Aucune hypothèse sur le signe des poids n'a été faite nulle part.

Toutes les paires: Floyd–Warshall

Changeons de problème. On veut maintenant $\delta (u,v)$ pour tous les couples de sommets: une matrice $n\times n$, et non plus un vecteur.

La première idée est bonne et il faut la garder en tête: lancer $n$ fois un algorithme à source unique. Avec Dijkstra et un tas binaire, cela coûte $O(n(n+m)\log n)$, ce qui, sur un graphe creux, bat tout le reste. Le défaut est l'hypothèse: les poids doivent être positifs. Avec Bellman–Ford, on obtient $O(n^{2}m)$, ce qui est très cher.

L'algorithme de Floyd–Warshall — Robert Floyd, 1962, sur une idée de Stephen Warshall pour la fermeture transitive — prend un autre chemin, accepte les poids négatifs, tient en cinq lignes et coûte $\Theta (n^3)$ quelle que soit la densité. Il travaille sur la matrice des poids $W$, où $W_{ij}$ vaut $w(i,j)$ s'il y a un arc, 0 si $i=j$, et sinon. Les sommets sont numérotés , comme les indices de tableau de ce cours.

L'indice du sommet intermédiaire

Toute la finesse est dans la définition de la quantité que l'on calcule, et c'est le seul point du chapitre qu'il faut vraiment mémoriser.

L'indice $k$ n'est donc ni une étape de temps, ni un nombre d'arêtes: c'est la taille de l'autorisation de transit. Chaque tour de boucle extérieure ouvre le graphe à un sommet intermédiaire de plus. C'est la confusion la plus fréquente sur cet algorithme, et elle explique pourquoi tant d'implémentations mettent la boucle sur $k$ au mauvais endroit.

Démonstration. Soit $p$ un chemin de $i$ à $j$ de poids minimal parmi ceux dont les sommets intermédiaires sont dans $\{0,\dots ,k-1\}$. En l'absence de circuit négatif, on peut le choisir élémentaire, donc il passe au plus une fois par chaque sommet. Deux cas s'excluent.

Premier cas: $p$ ne passe pas par le sommet $k-1$. Alors ses sommets intermédiaires sont dans $\{0,\dots ,k-2\}$, et $p$ est aussi un candidat pour $d_{ij}^{(k-1)}$; réciproquement tout candidat pour en est un pour . Le poids optimal est donc .

Second cas: $p$ passe par $k-1$, et une seule fois puisqu'il est élémentaire. Coupons $p$ en $p_1$, de $i$ à $k-1$, et $p_2$, de à . Par le théorème 7.2, et sont eux-mêmes de poids minimal entre leurs extrémités sous la contrainte considérée. Or leurs sommets intermédiaires sont ceux de privés de , donc dans : réalise et réalise . Le poids de est leur somme.

Le minimum des deux cas est la valeur cherchée, ce qui est exactement (7.6). $\square$

Le programme, et pourquoi $k$ est la boucle extérieure

def floyd_warshall(w):
    """Renvoie la matrice des distances entre toutes les paires."""
    n = len(w)
    d = [ligne[:] for ligne in w]
    for k in range(n):                       # le sommet intermediaire autorise
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] +

La récurrence (7.6) demande en principe de garder $d^{(k-1)}$ pendant qu'on calcule $d^{(k)}$, donc deux matrices. Le programme ci-dessus n'en utilise qu'une, et c'est licite: pendant la passe $k$, la ligne $k$ et la colonne $k$ ne changent pas. En effet $d_{ik}^{(k+1)}=\min (d_{ik}^{(k)},d_{ik}^{(k)}+d_{kk}^{(k)})$, et en l'absence de circuit négatif, si bien que le minimum vaut ; même chose pour la colonne. Les deux valeurs lues, et , sont donc les mêmes qu'on les prenne avant ou après la mise à jour, et une seule matrice suffit.

C'est cette justification, et elle seule, qui impose l'ordre des boucles. Si vous écrivez la boucle sur $k$ à l'intérieur, vous ne calculez plus la récurrence (7.6): vous mélangez des autorisations de transit différentes, et le résultat peut être faux. Ce n'est pas une inquiétude théorique. Sur le graphe de quatre sommets de l'exemple ci-dessous, la version avec $k$ à l'intérieur renvoie $d_{10}=7$ au lieu de $5$: une seule case sur seize, ce qui est exactement ce qu'il faut pour passer un test superficiel.

Le coût est $\Theta (n^3)$ tests de relaxation, quel que soit le graphe: trois boucles de $n$ tours, sans aucune sortie anticipée. L'espace est $\Theta (n^2)$. Comparons honnêtement avec $n$ exécutions de Dijkstra, en $O(n(n+m)\log n)$: pour un graphe dense, $m\approx n^2$, cela donne , et Floyd–Warshall gagne — en plus d'accepter les poids négatifs et de tenir en cinq lignes. Pour un graphe , , cela donne , et Dijkstra gagne d'un facteur , soit environ 50 000 pour un million de sommets. Le choix se fait donc sur la densité, pas sur l'élégance.

A*: Dijkstra avec un potentiel

Reprenons la question laissée ouverte au début: comment aller plus vite quand on ne veut la distance qu'entre deux sommets? Sur une carte routière, Dijkstra depuis Lausanne vers Zurich explore un disque à peu près circulaire autour de Lausanne, et il visitera Genève, Sion et Bâle avant d'atteindre son but. Pourtant vous savez, vous, que Genève est dans la mauvaise direction.

L'algorithme A* (Hart, Nilsson et Raphael, 1968) est la façon rigoureuse d'exploiter ce savoir. On se donne une heuristique $h(v)$, une estimation de la distance restante de $v$ à la destination $t$ — par exemple la distance à vol d'oiseau, calculable instantanément à partir des coordonnées —, et l'on modifie la priorité de la file: au lieu de classer les sommets par $d[v]$, on les classe par

c'est-à-dire par «coût déjà payé plus coût restant estimé». Un sommet dans la mauvaise direction a un grand $h$, il descend dans la file, et l'exploration s'étire vers la destination au lieu de s'étaler.

La bonne façon de comprendre A* n'est pas de le voir comme un algorithme nouveau, mais comme Dijkstra sur un graphe repondéré. Posons, pour un arc $(u,v)$,

Le long d'un chemin de $u_0$ à $u_k$, les termes $h$ se télescopent: le poids total devient $w(p)-h(u_0)+h(u_k)$. Comme et ne dépendent pas du chemin choisi mais seulement de ses extrémités, , et un plus court chemin pour en est un pour . Exécuter Dijkstra avec la priorité (7.7) revient exactement à l'exécuter avec les poids (7.8).

Dès lors, la condition de validité devient limpide. Dijkstra exige des poids positifs ou nuls, donc il faut $w_h(u,v)\ge 0$, c'est-à-dire

C'est la condition dite de consistance, ou de monotonie: l'heuristique doit satisfaire l'inégalité triangulaire. Avec $h(t)=0$, elle entraîne l'admissibilité, $h(v)\le \delta (v,t)$: l'heuristique ne surestime jamais. La distance à vol d'oiseau est consistante dès que les poids sont des longueurs réelles, puisqu'un segment de route est au moins aussi long que la ligne droite. Une heuristique qui surestime, elle, casse la garantie — et l'on retombe exactement sur le contre-exemple de la section précédente, parce que (7.8) fabrique alors un poids négatif.

Deux remarques pour situer l'algorithme. D'abord, A* ne change pas la complexité dans le pire des cas: avec $h\equiv 0$ il redevient Dijkstra, et une heuristique peut être vraie sans être informative. Son gain est pratique, parfois spectaculaire — sur un réseau routier, un facteur dix ou cent sur le nombre de sommets extraits n'est pas rare — mais il n'est garanti par aucun théorème général, et il dépend entièrement de la qualité de $h$. Nous ne citerons donc pas de chiffre de gain: il n'en existe pas qui soit indépendant de l'instance.

Ensuite, la même idée de potentiel sert ailleurs. L'algorithme de Johnson calcule, par un seul Bellman–Ford depuis une source artificielle reliée à tous les sommets, un potentiel $\pi$ tel que $w_{\pi }(u,v)=w(u,v)+\pi (u)-\pi (v)\ge 0$; il rend ainsi tous les poids positifs sans changer les plus courts chemins, puis lance Dijkstra. On obtient les distances entre toutes les paires d'un graphe en , ce qui bat Floyd–Warshall sur les graphes creux. C'est exactement la transformation que la section précédente annonçait comme impossible à obtenir en ajoutant une constante: elle existe, mais elle n'est pas constante — elle dépend du sommet.

Synthèse

• Le problème se pose sous quatre formes — une paire, une source, une destination, toutes les paires. La destination unique se ramène à la source unique en inversant les arcs; la paire unique ne se résout, dans le pire des cas et dans l'état de l'art, pas mieux que la source unique, parce qu'on ne peut certifier une distance sans avoir écarté tous les détours. La distance vaut $+\infty$ s'il n'y a pas de chemin et $-\infty$ si un circuit de poids négatif s'interpose.
• Tous les algorithmes du chapitre sont faits d'une seule opération, la relaxation (7.2). Elle préserve l'invariant $d[v]\ge \delta (s,v)$ à tout instant, elle ne fait jamais remonter une estimation, et elle fige définitivement la bonne valeur dès qu'elle est appliquée à la dernière arête d'un plus court chemin dont l'origine est déjà juste. La sous-structure optimale — tout sous-chemin d'un plus court chemin est un plus court chemin — est ce qui permet de recoller les morceaux, et son absence pour le plus long chemin est ce qui rend celui-ci difficile.
• Dijkstra fige à chaque tour le sommet non figé d'estimation minimale. Depuis $A$ sur le graphe témoin, il extrait dans l'ordre $A,C,B,D,E,F,G$ et produit ; la leçon est que vaut 3 , pas 4 par son arête directe. Le coût est avec un tas binaire, avec un tableau, le premier préférable sur un graphe creux. La correction repose sur un seul pas sensible: un sommet situé plus tôt sur un plus court chemin a une distance plus petite — vrai si et seulement si les poids sont positifs ou nuls.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4ᵉ éd., MIT Press — chapitre 22 pour la relaxation, Bellman–Ford, les graphes sans circuit et Dijkstra avec les démonstrations dont celles de ce chapitre s'inspirent; chapitre 23 pour Floyd–Warshall et Johnson.
• Cormen, Leiserson, Rivest & Stein, Algorithmique, 3ᵉ éd., Dunod — la traduction française des mêmes chapitres, utile pour fixer le vocabulaire: relâchement, plus court chemin à origine unique, fermeture transitive.
• Sedgewick & Wayne, Algorithms, 4ᵉ éd., Addison-Wesley — section 4.4, «Shortest Paths», pour l'implémentation avec file de priorité indexée et pour le traitement des graphes sans circuit.
• Kleinberg & Tardos, Algorithm Design, Pearson — sections 4.4 et 6.8, dont une lecture de Bellman–Ford comme programmation dynamique, qui éclaire le chapitre 10 de ce cours.
• Dijkstra, «A Note on Two Problems in Connexion with Graphs», Numerische Mathematik 1 (1959), p. 269–271 — l'article original, trois pages, parfaitement lisible aujourd'hui.
• Hart, Nilsson & Raphael, «A Formal Basis for the Heuristic Determination of Minimum Cost Paths», IEEE Transactions on Systems Science and Cybernetics 4 (1968), p. 100–107 — l'article fondateur d'A*, pour la condition d'admissibilité et sa démonstration.