Calculez les plus courts chemins

Votre application de navigation calcule en une fraction de seconde le trajet le plus rapide entre deux adresses, parmi des millions de rues. Un routeur internet choisit le chemin par lequel envoyer chaque paquet. Un jeu vidéo déplace ses personnages en contournant les obstacles. Derrière tout cela, un même problème : trouver un plus court chemin dans un graphe dont les arcs portent des longueurs.

Au chapitre 2, le BFS résolvait ce problème quand tous les arcs comptent pour 1. Ici, les arcs ont des valeurs quelconques (des minutes, des kilomètres, des coûts, parfois négatifs), et il faut des algorithmes plus fins. Notre fil rouge : aller de chez soi à l’INSA en traversant Rennes.

Le problème et son vocabulaire

Graphe valué et valeur d’un chemin

Un graphe valué associe à chaque arc $(i, j)$ une valuation $v(i, j)$ , un nombre réel. La valeur d’un chemin est la somme des valuations de ses arcs. On cherche, depuis une source $s$ , un chemin de valeur minimale vers chaque sommet : on note $\lambda(j)$ cette valeur optimale (la « distance » de $s$ à $j$ ).

Le fil rouge : de la maison à l’INSA

Six lieux : la maison (M), République (R), la gare (G), le Thabor (T), Beaulieu (B) et l’INSA (I). Les arcs donnent le temps de trajet en minutes (les sens uniques et les correspondances rendent le graphe orienté) :

Arc	M→R	M→G	R→G	R→T	R→B	G→T	G→B	T→B	T→I	B→I
Minutes	4	7	2	8	12	5	9	3	6	3

Le relâchement, brique commune

Tous les algorithmes de ce chapitre reposent sur la même opération, le relâchement (relaxation) d’un arc $(i, j)$ : « passer par $i$ améliore-t-il le meilleur chemin connu vers $j$ ? »

\lambda(j) \leftarrow \min\big(\lambda(j),\; \lambda(i) + v(i, j)\big)

On part de $\lambda(s) = 0$ et $\lambda(j) = +\infty$ ailleurs. Chaque fois qu’un relâchement améliore $\lambda(j)$ , on note $\text{pred}(j) = i$ . À la fin, les arcs $(\text{pred}(j), j)$ forment l’arborescence des chemins optimaux de racine $s$ : pour reconstituer le meilleur chemin vers $j$ , on remonte les prédécesseurs. Les algorithmes ne diffèrent que par l’ordre dans lequel ils relâchent les arcs.

Relâcher l'arc R → G, c'est comparer λ(R) + 2 = 6 à la valeur connue λ(G) = 7 et garder la meilleure.

Dijkstra : pour des valuations positives

Le principe

L’algorithme de Moore-Dijkstra suppose que toutes les valuations sont positives ou nulles. Il maintient un ensemble $S$ de sommets dont la distance est définitive. À chaque étape :

choisir, hors de $S$ , le sommet $i$ de $\lambda(i)$ minimal et l’ajouter à $S$ (sa valeur est figée) ;
relâcher tous les arcs qui sortent de $i$ .

L’intuition : le sommet non figé le plus proche ne peut pas être amélioré plus tard, car tout autre chemin passerait par un sommet déjà plus loin, et les arcs positifs ne peuvent qu’allonger le trajet.

Depuis la maison M. Chaque ligne indique le sommet figé et les valeurs après relâchement de ses arcs (en gras, les valeurs définitives).

Étape	Sommet figé	M	R	G	T	B	I
0		0	∞	∞	∞	∞	∞
1	M	0	4	7	∞	∞	∞
2	R		4	6 (par R)	12	16	∞
3	G			6	11 (par G)	15 (par G)	∞
4	T				11	14 (par T)	17
5	B					14	17
6	I						17

À l’étape 5, passer par B donnerait $14 + 3 = 17$ pour I, pas mieux que 17 : on garde le prédécesseur T. Le trajet optimal vers l’INSA dure 17 minutes : M → R → G → T → I. Remarquez que l’arc direct M → G (7 minutes) est battu par le détour M → R → G (6 minutes).

Les valeurs se figent dans l'ordre croissant 0, 4, 6, 11, 14, 17. L'arborescence en vert donne le trajet M → R → G → T → I.

Complexité et code

Avec un simple tableau, choisir le minimum coûte $O(n)$ à chaque étape : Dijkstra est en $O(n^2)$ . Avec un tas (file de priorité), on passe à $O((n + m) \log n)$ , ce qui est bien meilleur sur un graphe creux comme un réseau routier.

import heapq

def dijkstra(succ, source):
    """succ : sommet -> liste de (successeur, valuation >= 0)."""
    lam = {x: float("inf") for x in succ}
    pred = {x: None for x in succ}
    lam[source] = 0
    tas = [(0, source)]
    figes = set()
    while tas:
        d, i = heapq.heappop(tas)
        if i in figes:
            continue                      # entrée périmée du tas
        figes.add(i)                      # lambda(i) est définitif
        for j, v in succ[i]:
            if d + v < lam[j]:            # relâchement
                lam[j], pred[j] = d + v, i
                heapq.heappush(tas, (lam[j], j))
    return lam, pred

rennes = {"M": [("R", 4), ("G", 7)], "R": [("G", 2), ("T", 8), ("B", 12)],
          "G": [("T", 5), ("B", 9)], "T": [("B", 3), ("I", 6)],
          "B": [("I", 3)], "I": []}
lam, pred = dijkstra(rennes, "M")
print(lam["I"])                            # 17

Avec un arc négatif, le sommet le plus proche n'est pas forcément définitif : le détour par b coûte 1, moins que l'arc direct.

Bellman-Ford : pour des valuations quelconques

Relâcher tout, plusieurs fois

Quand des arcs sont négatifs (un gain, un remboursement, une voiture électrique qui récupère de l’énergie en descente), on utilise l’algorithme de Bellman-Ford (appelé simplement algorithme de Bellman ou de Ford en cours). Il ne fige rien : il relâche tous les arcs, puis recommence, jusqu’à ce qu’un passage complet ne change plus rien.

Pourquoi cela termine-t-il ? S’il n’y a pas de circuit absorbant, un plus court chemin peut être choisi élémentaire, donc avec au plus $n - 1$ arcs. Après le passage numéro $k$ , toutes les valeurs des plus courts chemins d’au plus $k$ arcs sont correctes. Donc au bout de $n - 1$ passages, tout est stable.

def bellman_ford(sommets, arcs, source):
    """arcs : liste de (i, j, valuation). Lève une erreur en cas de circuit absorbant."""
    lam = {x: float("inf") for x in sommets}
    lam[source] = 0
    for _ in range(len(sommets)):
        change = False
        for i, j, v in arcs:
            if lam[i] + v < lam[j]:
                lam[j] = lam[i] + v
                change = True
        if not change:
            return lam                    # stable : c'est fini
    raise ValueError("circuit absorbant accessible depuis la source")

Le cas des graphes sans circuit

Si le graphe est sans circuit, il y a encore mieux : on relâche les arcs sortants de chaque sommet dans l’ordre topologique (chapitre 4). Un seul passage suffit, en $O(n + m)$ , quels que soient les signes des valuations. Et comme il n’y a pas de circuit, on peut aussi bien chercher des plus longs chemins en remplaçant min par max : c’est la clé de l’ordonnancement de projets, au chapitre suivant.

Floyd-Warshall : tous les couples d’un coup

Pour connaître la distance entre tous les couples de sommets (une matrice de temps de trajet entre toutes les villes, par exemple), on pourrait lancer $n$ fois Dijkstra. L’algorithme de Floyd-Warshall fait plus simple : c’est Roy-Warshall (chapitre 3) en version valuée.

d(x, y) \leftarrow \min\big(d(x, y),\; d(x, k) + d(k, y)\big) \quad \text{pour } k = 1, \dots, n

où $d(x, y)$ est la meilleure valeur connue d’un chemin de $x$ à $y$ dont les sommets intermédiaires sont parmi $1, \dots, k$ . On part de la matrice des valuations (0 sur la diagonale, $+\infty$ en l’absence d’arc). La complexité est en $O(n^3)$ , et l’algorithme accepte les arcs négatifs ; un circuit absorbant se repère à une valeur négative sur la diagonale.

À chaque étape k, Floyd-Warshall autorise un intermédiaire de plus ; les infinis disparaissent un à un jusqu'à la matrice finale du texte.

Quel algorithme choisir ?

Situation	Algorithme	Complexité
Arcs tous de longueur 1	BFS	$O(n + m)$
Valuations positives, une source	Dijkstra (avec tas)	$O((n + m) \log n)$
Valuations quelconques, une source	Bellman-Ford	$O(nm)$
Graphe sans circuit, valuations quelconques	ordre topologique	$O(n + m)$
Tous les couples	Floyd-Warshall	$O(n^3)$

import networkx as nx

G = nx.DiGraph()
G.add_weighted_edges_from([(i, j, v) for i, succ in rennes.items() for j, v in succ])
print(nx.dijkstra_path(G, "M", "I"), nx.dijkstra_path_length(G, "M", "I"))   # 17
print(nx.bellman_ford_path_length(G, "M", "I"))
distances = dict(nx.floyd_warshall(G))                  # tous les couples

En résumé

Dans un graphe valué, on cherche depuis une source les chemins de valeur minimale ; ils forment une arborescence des chemins optimaux, codée par le tableau des prédécesseurs.
Tous les algorithmes relâchent des arcs : $\lambda(j) \leftarrow \min(\lambda(j), \lambda(i) + v(i, j))$ . Un circuit absorbant (négatif) rend le problème sans solution.
Dijkstra fige à chaque étape le sommet le plus proche ; il exige des valuations positives et coûte $O(n^2)$ , ou $O((n + m) \log n)$ avec un tas.
Bellman-Ford relâche tous les arcs jusqu’à stabilité ; il accepte les valuations négatives, coûte $O(nm)$ et détecte les circuits absorbants.
Sur un graphe sans circuit, un passage dans l’ordre topologique suffit, pour les plus courts comme pour les plus longs chemins.
Floyd-Warshall calcule tous les couples en $O(n^3)$ : c’est Roy-Warshall avec (min, +).

Exercices

Exercice · Une route fermée

facile

Des travaux ferment la liaison Gare → Thabor (G→T). Recalculez avec Dijkstra la durée du trajet de la maison à l’INSA. Quel est le nouveau trajet ?

Voir la solution

On fige M (0) : R = 4, G = 7.
On fige R (4) : G = 6, T = 12, B = 16.
On fige G (6) : G n’a plus que l’arc G→B, qui donne B = 15.
On fige T (12) : B = min(15, 15) = 15 (inchangé), I = 18.
On fige B (15) : I = min(18, 18) = 18.
On fige I (18).

Le trajet dure maintenant 18 minutes. Il y a deux trajets optimaux : M → R → T → I et M → R → G → B → I, tous deux de 18 minutes.

En code

Python
R

import heapq

def dijkstra(succ, source):
    lam = {x: float("inf") for x in succ}
    pred = {x: None for x in succ}
    lam[source] = 0
    tas, figes = [(0, source)], set()
    while tas:
        d, i = heapq.heappop(tas)
        if i in figes:
            continue
        figes.add(i)                           # lambda(i) est définitif
        for j, v in succ[i]:
            if d + v < lam[j]:                 # relâchement
                lam[j], pred[j] = d + v, i
                heapq.heappush(tas, (lam[j], j))
    return lam, pred

rennes = {"M": [("R", 4), ("G", 7)], "R": [("G", 2), ("T", 8), ("B", 12)],
          "G": [("B", 9)],                       # l'arc G -> T est fermé
          "T": [("B", 3), ("I", 6)], "B": [("I", 3)], "I": []}
lam, pred = dijkstra(rennes, "M")
print(lam)   # {'M': 0, 'R': 4, 'G': 6, 'T': 12, 'B': 15, 'I': 18}
chemin, x = [], "I"
while x:
    chemin.append(x)
    x = pred[x]
print(chemin[::-1])   # ['M', 'R', 'T', 'I'] (M, R, G, B, I dure aussi 18)

lieux <- c("M", "R", "G", "T", "B", "I")
V <- matrix(Inf, 6, 6, dimnames = list(lieux, lieux))
V["M", "R"] <- 4; V["M", "G"] <- 7; V["R", "G"] <- 2; V["R", "T"] <- 8; V["R", "B"] <- 12
V["G", "B"] <- 9; V["T", "B"] <- 3; V["T", "I"] <- 6; V["B", "I"] <- 3   # plus d'arc G -> T

dijkstra <- function(V, source) {
  lam <- setNames(rep(Inf, nrow(V)), rownames(V)); lam[source] <- 0
  pred <- setNames(rep(NA, nrow(V)), rownames(V))
  fige <- setNames(rep(FALSE, nrow(V)), rownames(V))
  while (!all(fige)) {
    i <- names(which.min(ifelse(fige, Inf, lam)))   # sommet non figé le plus proche
    fige[i] <- TRUE
    mieux <- lam[i] + V[i, ] < lam                   # relâchement des arcs sortants
    lam[mieux] <- lam[i] + V[i, mieux]; pred[mieux] <- i
  }
  list(lam = lam, pred = pred)
}

res <- dijkstra(V, "M")
res$lam                       # M 0, R 4, G 6, T 12, B 15, I 18
chemin <- c(); x <- "I"
while (!is.na(x)) { chemin <- c(x, chemin); x <- res$pred[[x]] }
chemin                        # "M" "R" "T" "I" (M, R, G, B, I dure aussi 18)

Exercice · Détecter un circuit absorbant

moyen

Graphe de sommets $s$ , $a$ , $b$ , $c$ avec les arcs $s \to a$ (1), $a \to b$ (2), $b \to c$ (-4), $c \to a$ (1). Déroulez Bellman-Ford depuis $s$ en relâchant les arcs dans cet ordre. Que se passe-t-il ? Que vaut le circuit $a \to b \to c \to a$ ?

Voir la solution

Passage 1 : $\lambda(a) = 1$ , $\lambda(b) = 3$ , $\lambda(c) = -1$ , puis $c \to a$ donne $\lambda(a) = \min(1, 0) = 0$ .
Passage 2 : $\lambda(b) = 2$ , $\lambda(c) = -2$ , $\lambda(a) = -1$ .
Passage 3 : $\lambda(b) = 1$ , $\lambda(c) = -3$ , $\lambda(a) = -2$ .
Passage 4 ( $n = 4$ sommets) : les valeurs baissent encore ( $\lambda(b) = 0$ , $\lambda(c) = -4$ , $\lambda(a) = -3$ ).

Les valeurs changent encore au $n$ -ième passage : il y a un circuit absorbant. En effet, le circuit $a \to b \to c \to a$ vaut $2 - 4 + 1 = -1 \lt 0$ : chaque tour fait gagner une unité, sans limite. Aucun plus court chemin n’existe vers $a$ , $b$ ou $c$ .

En code

Python
R

sommets = ["s", "a", "b", "c"]
arcs = [("s", "a", 1), ("a", "b", 2), ("b", "c", -4), ("c", "a", 1)]

lam = {x: float("inf") for x in sommets}
lam["s"] = 0
for passage in range(1, len(sommets) + 1):
    change = False
    for i, j, v in arcs:                       # on relâche tous les arcs, dans l'ordre
        if lam[i] + v < lam[j]:
            lam[j] = lam[i] + v
            change = True
    print(passage, lam)
print("circuit absorbant" if change else "stable")
# 1 {'s': 0, 'a': 0, 'b': 3, 'c': -1}
# 2 {'s': 0, 'a': -1, 'b': 2, 'c': -2}
# 3 {'s': 0, 'a': -2, 'b': 1, 'c': -3}
# 4 {'s': 0, 'a': -3, 'b': 0, 'c': -4}
# circuit absorbant
print(2 - 4 + 1)   # -1 : valeur du circuit a -> b -> c -> a

arcs <- data.frame(i = c("s", "a", "b", "c"), j = c("a", "b", "c", "a"), v = c(1, 2, -4, 1))
lam <- c(s = 0, a = Inf, b = Inf, c = Inf)

for (passage in 1:length(lam)) {
  change <- FALSE
  for (k in 1:nrow(arcs)) {                    # on relâche tous les arcs, dans l'ordre
    if (lam[arcs$i[k]] + arcs$v[k] < lam[arcs$j[k]]) {
      lam[arcs$j[k]] <- lam[arcs$i[k]] + arcs$v[k]; change <- TRUE
    }
  }
  cat(passage, ":", lam, "\n")
}
if (change) "circuit absorbant" else "stable"
# 1 : 0 0 3 -1
# 2 : 0 -1 2 -2
# 3 : 0 -2 1 -3
# 4 : 0 -3 0 -4
# "circuit absorbant"

Exercice · Adapter Floyd-Warshall

difficile

Des camions doivent traverser un réseau de routes, et chaque arc $(x, y)$ porte une hauteur maximale autorisée $h(x, y)$ (ponts, tunnels). La hauteur admise par un chemin est la plus petite hauteur de ses arcs. On cherche, pour chaque couple $(x, y)$ , la plus grande hauteur de camion qui peut aller de $x$ à $y$ . Adaptez Floyd-Warshall : quelle est la mise à jour, et quelle valeur initiale faut-il en l’absence d’arc ?

Voir la solution

On note $H(x, y)$ la meilleure hauteur connue d’un chemin de $x$ à $y$ . Passer par $k$ donne un chemin dont la hauteur admise est le minimum des deux morceaux, $\min(H(x, k), H(k, y))$ , et l’on veut la plus grande possible. La mise à jour devient :

H(x, y) \leftarrow \max\Big(H(x, y),\; \min\big(H(x, k),\; H(k, y)\big)\Big)

C’est Roy-Warshall avec le couple d’opérations (max, min) au lieu de (min, +). Initialisation : $H(x, y) = h(x, y)$ s’il y a un arc, $H(x, y) = 0$ sinon (aucun camion ne passe), et $H(x, x) = +\infty$ (rester sur place n’impose aucune contrainte). Les boucles sont les mêmes, avec $k$ à l’extérieur, et la complexité reste en $O(n^3)$ . Ce problème s’appelle le chemin de capacité maximale (widest path) ; il revient aussi dans les réseaux de télécommunication, pour trouver le chemin de plus grande bande passante.

En code

Python
R

INF = float("inf")
# Hauteurs maximales (en mètres) sur un petit réseau de 4 carrefours
hauteur = {(1, 2): 4.0, (2, 3): 3.8, (1, 3): 3.2, (3, 4): 4.5, (2, 4): 3.0}
n = 4
H = [[INF if x == y else hauteur.get((x + 1, y + 1), 0) for y in range(n)] for x in range(n)]

for k in range(n):                              # k à l'extérieur, comme Roy-Warshall
    for x in range(n):
        for y in range(n):
            H[x][y] = max(H[x][y], min(H[x][k], H[k][y]))   # couple (max, min)

print(H[0][3])   # 3.8 : par 1 -> 2 -> 3 -> 4, meilleur que 1 -> 2 -> 4 (3.0) et 1 -> 3 -> 4 (3.2)
print(H[3][0])   # 0 : aucun chemin de 4 vers 1

# Hauteurs maximales (en mètres) sur un petit réseau de 4 carrefours
n <- 4
H <- matrix(0, n, n); diag(H) <- Inf           # 0 : pas d'arc ; +Inf : rester sur place
H[1, 2] <- 4.0; H[2, 3] <- 3.8; H[1, 3] <- 3.2; H[3, 4] <- 4.5; H[2, 4] <- 3.0

for (k in 1:n)                                  # k à l'extérieur, comme Roy-Warshall
  H <- pmax(H, outer(H[, k], H[k, ], pmin))     # couple (max, min), pour tous les (x, y) à la fois

H[1, 4]   # 3.8 : par 1 -> 2 -> 3 -> 4, meilleur que 1 -> 2 -> 4 (3.0) et 1 -> 3 -> 4 (3.2)
H[4, 1]   # 0 : aucun chemin de 4 vers 1