Plus court chemin : Dijkstra

2. Le principe de Dijkstra

On fixe un sommet de départ et on veut la distance (poids total minimal d'un chemin) du départ vers tous les autres sommets. L'idée de Dijkstra est de faire grandir, étape par étape, un ensemble de sommets dont on connaît la distance définitive.

3. L'algorithme en Python (version simple)

Voici la version dite « simple » : à chaque étape on cherche le minimum par un parcours de tous les sommets. Pas besoin de structure sophistiquée — un dictionnaire dist et un ensemble finalises suffisent.

import math

def dijkstra(g, depart):
    dist = {s: math.inf for s in g}      # distances provisoires
    dist[depart] = 0
    finalises = set()                    # sommets déjà finalisés
    while len(finalises) < len(g):
        # 1) choisir le non-finalisé de plus petite distance
        u = None
        meilleure = math.inf
        for s in g:
            if s not in finalises and dist[s] < meilleure:
                meilleure = dist[s]
                u = s
        if u is None:                    # les restants sont à l'infini
            break                        # -> inatteignables, on s'arrête
        # 2) finaliser u
        finalises.add(u)
        # 3) relâcher les arêtes sortantes de u
        for v, w in g[u].items():
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

Trace pas à pas

Déroulons dijkstra(g, "A") sur le graphe de la partie 1. À chaque étape : on choisit le sommet non finalisé de plus petite distance (colonne « finalisé »), on le fige, puis on relâche ses arêtes. Le tableau donne l'état de dist après relâchement.

4. Pourquoi ça marche : la finalisation est définitive

5. Le piège : les poids négatifs

Un contre-exemple concret. Quatre sommets, une seule arête négative (D→B) :

g = {
    "A": {"B": 1, "D": 3},
    "B": {"C": 5},
    "C": {},
    "D": {"B": -3},
}
# Vrai plus court chemin de A vers B :
#   direct  A->B        = 1
#   détour  A->D->B    = 3 + (-3) = 0   <-- meilleur !
# donc vrai plus court chemin A->C = A->D->B->C = 0 + 5 = 5

Déroulons dijkstra(g, "A"). On finalise A (0) et on relâche : dist[B]=1, dist[D]=3. Le plus petit non finalisé est B à 1 : Dijkstra finalise B à 1 et relâche aussitôt B→C, d'où dist[C]=1+5=6. Ensuite il finalise D (3) et relâche D→B : 3+(−3)=0 < 1, donc dist[B] tombe à 0 — mais B est déjà finalisé : son arête B→C ne sera jamais re-relâchée. Bilan : le programme renvoie dist[C]=6, alors que le vrai plus court chemin A→D→B→C vaut 5. Dijkstra a finalisé B trop tôt et s'en est servi pour calculer C avant de découvrir, via l'arête négative, le meilleur chemin vers B. La garantie du théorème 4.1 tombe.

6. Application et coût

Complexité de la version simple. La boucle while tourne $n$ fois (une finalisation par tour). À chaque tour, la recherche du minimum balaie les $n$ sommets : coût $O(n)$. Les relâchements, cumulés sur toute l'exécution, parcourent chaque arête une fois : $O(m)$ au total. Le terme dominant est la recherche du minimum :

$$O(n^2+m)=O(n^2)(\text{car }m\le n^2).$$

7. Exercices corrigés

import math

def dijkstra_pred(g, depart):
    dist = {s: math.inf for s in g}
    dist[depart] = 0
    pred = {depart: None}
    finalises = set()
    while len(finalises) < len(g):
        u, meilleure = None, math.inf
        for s in g:
            if s not in finalises and dist[s] < meilleure:
                meilleure, u = dist[s], s
        if u is None:
            break
        finalises.add(u)
        for v, w in g[u].items():
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                pred[v] = u          # v est atteint au mieux via u
    return dist, pred

def chemin(pred, depart, arrivee):
    if arrivee not in pred:          # inatteignable
        return None
    ch = [arrivee]
    while ch[-1] != depart:
        ch.append(pred[ch[-1]])      # on remonte de prédécesseur en prédécesseur
    ch.reverse()                     # on avait la liste à l'envers
    return ch