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$.

Principe de l’algorithme (suite)

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).

Principe de l’algorithme (suite)

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.

Exemple détaillé (suite)

Exemple détaillé (suite)

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.

Exemple détaillé (suite)

Exemple détaillé (suite)

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.

Implémentation en Python (suite)

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 = list(graphe.keys())

    while len(non_traites) > 0:
        # 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

Algorithme de Dijkstra (suite)

float("inf") est une valeur flottante plus grande que tout nombre. Elle représente ici une distance infinie : au départ, aucun sommet autre que depart n’est atteint.

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.

Exercice (suite)

Vérifiez votre compréhension

1. L’algorithme de Dijkstra fonctionne-t-il avec des poids négatifs ? Pourquoi ?
   Réponse

   Non. Dijkstra repose sur le fait qu'un sommet traité a sa distance définitive. Un poids négatif pourrait permettre de trouver un chemin plus court vers un sommet déjà traité, ce qui invaliderait le résultat.
2. Quelle est la différence entre le parcours en largeur (BFS) et l’algorithme de Dijkstra pour trouver un plus court chemin ?
   Réponse

   Le BFS trouve le plus court chemin en nombre d'arêtes (graphe non pondéré). Dijkstra trouve le plus court chemin en poids total (graphe pondéré à poids positifs). Dans un graphe non pondéré, les deux donnent le même résultat.
3. Comment reconstitue-t-on le chemin une fois l’algorithme terminé ?
   Réponse

   On remonte les prédécesseurs depuis le sommet d'arrivée jusqu'au sommet de départ, puis on inverse la liste obtenue.

L'essentiel à retenir

• L’algorithme de Dijkstra calcule les plus courts chemins depuis un sommet de départ vers tous les autres sommets d’un graphe pondéré à poids positifs.
• Il procède par sélection gloutonne : à chaque étape, il traite le sommet non encore visité dont la distance provisoire est minimale.
• La reconstitution du chemin se fait en remontant le tableau des prédécesseurs depuis le sommet d’arrivée.
• La complexité est $O(n^2)$ avec une recherche linéaire du minimum, améliorable à $O((n+m) \log n)$ avec un tas.
• Dijkstra ne fonctionne pas avec des poids négatifs ; pour ce cas, on utilise l’algorithme de Bellman-Ford (hors programme).