CHAPITRE 3
Plus courts chemins et programmation
dynamique
Les problèmes de plus courts chemins apparaissent naturellement dans des contextes
variés. Ils peuvent apparaı̂tre comme modélisation de problèmes opérationnels (trajet le plus
rapide, ou le moins cher, gestion optimal d’un stock, plan d’investissement optimal, etc.),
ils sont aussi fréquemment des sous-problèmes d’autres problèmes d’optimisation (flot de
coût minimum – Chapitre 5 – ou en théorie de l’ordonnancement – Chapitre 10). Sous cette
appellation anodine de plus court chemin, nous verrons qu’il se cache une réalité extrêmement
variée, tant du point de vue de la complexité que des types d’algorithmes mis en œuvre. Le
graphe peut être orienté ou non, les arêtes ou les arcs avoir des poids positifs ou quelconque,...
Un cas particulier important est la programmation dynamique qui traite des situations où des
décisions doivent être prises de manière séquentielle, chaque décision faisant passer le système
d’un état à un autre. Ce passage d’un état à un autre s’appelle une transition. On suppose
qu’un coût est associé à chaque transition. L’objectif de la programmation dynamique est
de minimiser le coût de la suite des transitions, suite qu’on appelle trajectoire.
3.1 Cas du graphe orienté et programmation dynamique
3.1.1 Les poids sont positifs : algorithme de Dijkstra
Le cas le plus naturel est le cas du graphe orienté avec des poids strictement positifs sur
les arcs. En effet, le problème du trajet le plus court dans un réseau (routier, de transport,
informatique, etc.) rentre dans ce cadre. Le temps de parcours d’un arc, ou sa longueur, sont
dans ces contextes strictement positifs.
En 1959, Dijkstra proposa le premier algorithme efficace. On suppose que l’on a un graphe
orienté D = (V, A), avec une fonction de poids w : A → R+ . On se fixe un sommet s de
départ et un sommet t d’arrivée. On veut le chemin de plus petit poids (le poids d’un chemin
étant la somme des poids de ses arcs), ou autrement dit le plus court chemin allant de s
à t. Noter que dans un graphe dont tous les poids sont positifs, il existe toujours un plus
court chemin qui est un chemin élémentaire (avec répétition de sommets interdite) car si
le plus court chemin passe par un circuit, on peut supprimer ce circuit sans détériorer le
poids du chemin. Si tous les poids sont strictement positifs, les notions de plus court chemin,
plus court chemin simple (avec répétition d’arcs interdite) et plus court chemin élémentaire
CHAPITRE 3. PLUS COURTS CHEMINS ET PROGRAMMATION DYNAMIQUE 30
(avec répétition de sommets interdite) coı̈ncident puisqu’alors suivre un circuit détériore
strictement le poids du chemin.
L’algorithme de Dijkstra va calculer les plus courts chemins démarrant en s pour tous
les sommets d’arrivée possibles, donc en particulier pour t.
Au cours de l’algorithme, on maintient un ensemble U ⊆ V et une fonction λ : V → R+ .
On dit que λ(v) est le label courant de v. Ce label est la meilleure évaluation courante du
poids du plus court chemin de s à v. On commence avec U := V et λ(s) := 0 et λ(v) := +∞
pour v 6= s. Ensuite, on répète la chose suivante de manière itérative :
Choisir u minimisant λ(u) pour u ∈ U . Pour chaque (u, v) ∈ δ + (u) tel
que λ(v) > λ(u) + w(u, v), redéfinir λ(v) := λ(u) + w(u, v). Redéfinir
U := U \ {u}.
On s’arrête lorsque λ(u) = +∞ pour tout u ∈ U . La fonction λ donne alors les distances de
s à tout sommet que l’on peut atteindre en partant de s. Les sommets dans U à la fin de
l’algorithme sont ceux qui ne peuvent être atteints depuis s.
De plus, si pour chaque v 6= s, on garde en mémoire le dernier arc a = (u, v) pour lequel
on a redéfini λ(v) := λ(u) + w(a), on peut reconstruire l’ensemble des plus courts chemins
partant de s.
Il est clair que le nombre d’itérations est au plus |V |, et chaque itération prend un temps
O(n). L’algorithme a donc une fonction de complexité qui est en O(n2 ). D’où le théorème :
Théorème 3.1. Etant donnés un graphe orienté D = (V, A), un sommet s ∈ V et une
fonction de poids w : A → R+ , un ensemble de plus courts chemins de s à tout sommet
v ∈ V peut être calculé en O(n2 ).
Eléments de preuve. Pour démontrer le théorème, il faut simplement voir que lorsque u est retiré de U
dans l’itération au-dessus, λ(u) est la vraie distance de s à u (la preuve de cette assertion est laissée en
exercice).
Remarque
En utilisant de bonnes structures de données, il est possible d’obtenir une complexité de
O(m + n log n).
Exemple
En appliquant l’algorithme de Dijkstra sur la Figure 3.1, on obtient le tableau suivant
indiquant les valeurs successives de λ pour chaque sommet.
