Algorithme de Dijkstra

Ouverture hors programme de terminale NSI. L’algorithme de Dijkstra n’est pas exigible au baccalauréat ; il prolonge le chapitre sur les parcours de graphes.

Principe de l’algorithme

Pour déterminer le plus court chemin entre deux sommets d’un graphe pondéré, on pourrait essayer d’énumérer tous les chemins possibles et comparer leurs longueurs. Mais cette approche devient impraticable dès que le graphe est un peu grand.

E. W. Dijkstra , informaticien néerlandais (1930–2002), a proposé en 1959 un algorithme bien plus efficace. Son principe repose sur une idée fondamentale : si le plus court chemin de $s_0$ à un sommet $S$ passe par les sommets intermédiaires $s_1, s_2, \ldots, s_k$, alors chaque sous-chemin $s_0 \to s_1 \to \cdots \to s_i$ est lui-même un plus court chemin de $s_0$ à $s_i$.

L’algorithme construit donc la solution de proche en proche :

1. On initialise la distance du sommet de départ à 0 et celle de tous les autres sommets à $+\infty$.
2. À chaque itération, on sélectionne parmi les sommets non encore traités celui dont la distance provisoire est minimale.
3. Pour chacun de ses voisins, on vérifie si passer par le sommet sélectionné offre un chemin plus court que celui connu jusque-là. Si oui, on met à jour la distance et le prédécesseur.
4. On répète jusqu’à avoir traité tous les sommets (ou atteint le sommet d’arrivée).

Condition importante : l’algorithme de Dijkstra ne fonctionne que si tous les poids sont positifs ou nuls. Un poids négatif pourrait invalider les distances déjà calculées.

Grâce à sa performance, cet algorithme est utilisé par les logiciels d’optimisation de trajets (navigateurs GPS, site RATP) et les protocoles de routage réseau (OSPF).

Exemple détaillé

Le graphe ci-dessous représente un réseau routier orienté. Chaque arc a un poids correspondant à la distance en kilomètres. On cherche le plus court chemin de A à H.

On remplit le tableau étape par étape. À chaque ligne, on sélectionne le sommet non traité de distance minimale, puis on met à jour les distances de ses voisins.

Lecture du tableau : la notation $7_A$ signifie « distance 7, en venant de A ». Le sommet D est atteint directement depuis A (distance 18), ce qui est meilleur que le passage par B puis C ($7 + 8 + 6 = 21$). F est ensuite mis à jour lors du traitement de D : $18 + 11 = 29 < 33$.

Reconstitution du chemin : on part de H et on remonte les prédécesseurs : $H \leftarrow G \leftarrow F \leftarrow D \leftarrow A$. Le plus court chemin de A à H est donc :

$$A \to D \to F \to G \to H \quad \text{(distance : 41 km)}$$

Implémentation en Python

On représente le graphe pondéré par un dictionnaire de dictionnaires : chaque sommet associe à ses voisins le poids de l’arc correspondant.

graphe = {
    "A": {"B": 7, "E": 14, "D": 18},
    "B": {"C": 8},
    "C": {"D": 6},
    "D": {"A": 18, "F": 11},
    "E": {"F": 19},
    "F": {"G": 4, "H": 13, "C": 5},
    "G": {"H": 8},
    "H": {"C": 9}
}

Algorithme de Dijkstra

def dijkstra(graphe, depart):
    """Renvoie les distances minimales et les prédécesseurs
    depuis le sommet de départ."""
    # Initialisation
    distances = {s: float("inf") for s in graphe}
    distances[depart] = 0
    predecesseurs = {s: None for s in graphe}
    non_traites = set(graphe.keys())

    while non_traites:
        # Sélectionner le sommet non traité de distance minimale
        sommet = min(non_traites, key=lambda s: distances[s])
        non_traites.remove(sommet)

        # Mettre à jour les distances des voisins
        for voisin, poids in graphe[sommet].items():
            nouvelle_dist = distances[sommet] + poids
            if nouvelle_dist < distances[voisin]:
                distances[voisin] = nouvelle_dist
                predecesseurs[voisin] = sommet

    return distances, predecesseurs

Reconstitution du chemin

def plus_court_chemin(graphe, depart, arrivee):
    """Renvoie le plus court chemin et sa distance."""
    distances, predecesseurs = dijkstra(graphe, depart)
    chemin = []
    sommet = arrivee
    while sommet is not None:
        chemin.append(sommet)
        sommet = predecesseurs[sommet]
    chemin.reverse()
    return chemin, distances[arrivee]

Test

chemin, distance = plus_court_chemin(graphe, "A", "H")
print(f"Chemin : {' → '.join(chemin)}")
print(f"Distance : {distance} km")

Chemin : A → D → F → G → H
Distance : 41 km

Complexité

Avec l’implémentation ci-dessus (recherche du minimum par parcours linéaire), la complexité est $O(n^2)$ où $n$ est le nombre de sommets. En effet, à chaque itération, on parcourt les sommets non traités pour trouver celui de distance minimale.

On peut améliorer cette complexité à $O((n + m) \log n)$ en utilisant un tas (heap) pour extraire efficacement le minimum. Ici, $m$ désigne le nombre d’arêtes. Cette optimisation est hors programme mais explique pourquoi Dijkstra est utilisable sur de très grands graphes (millions de sommets dans les réseaux routiers).

Exercice

En utilisant l’algorithme de Dijkstra, déterminer le plus court chemin de l’entrée E à la sortie S dans le graphe ci-dessous.