L'Algorithme de Dijkstra expliqué, pas à pas

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

Qu'est-ce que l'Algorithme de Dijkstra ?

L'algorithme de Dijkstra, publié par Edsger W. Dijkstra en 1959, trouve le plus court chemin depuis une seule source vers tous les autres nœuds d'un graphe pondéré. Il fonctionne sur les graphes orientés comme non orientés, avec une condition ferme : chaque poids d'arête doit être non négatif.

Voyez le graphe comme un réseau routier. Les nœuds sont des carrefours, les arêtes des routes, et chaque poids est le temps ou la distance pour parcourir cette route. L'algorithme de Dijkstra répond à la question que pose toute application de navigation : quel est l'itinéraire le plus rapide d'où je suis vers partout ailleurs ? C'est un élément de la famille plus large traitée dans les algorithmes de plus courts chemins, et un incontournable de la feuille de route de la théorie des graphes.

L'Idée Centrale

L'algorithme de Dijkstra est glouton. Il conserve une distance la plus courte provisoire vers chaque nœud et répète un geste simple :

Visitez toujours le nœud non visité ayant la plus petite distance connue, puis servez-vous-en pour améliorer ses voisins.

L'intuition qui rend cela correct : comme tous les poids sont non négatifs, dès que vous choisissez le nœud non visité le plus proche, aucun chemin futur ne pourra l'atteindre à moindre coût. Ainsi, à l'instant où un nœud est choisi, sa distance est définitive. Cette seule garantie constitue tout l'algorithme.

Concrètement, l'algorithme entretient :

• Une distance vers chaque nœud, toutes commençant à l'infini sauf la source, qui vaut 0.
• Une file de priorité (tas-min) qui rend toujours le nœud non visité le plus proche.
• Un ensemble de nœuds définitifs dont la distance la plus courte est arrêtée.

Améliorer un voisin s'appelle la relaxation : si le chemin passant par le nœud courant est plus court que la distance enregistrée du voisin, vous l'abaissez.

Comment ça Marche, Pas à Pas

Exécutons Dijkstra depuis le nœud A sur ce graphe pondéré. Les arêtes bleues formeront l'arbre final des plus courts chemins, et le nombre à côté de chaque nœud est sa distance la plus courte finale depuis A.

Voici le déroulé. À chaque étape, nous figeons le nœud non visité le plus proche (en gras) et relaxons ses voisins. ∞ signifie "pas encore atteint".

Remarquez l'étape trois : visiter C a abaissé B de 4 à 3, car la route A → C → B (2 + 1) bat l'arête directe A → B (4). C'est la relaxation à l'œuvre. Voir cela se dérouler sur un graphe en direct rend le schéma immédiat, ce que vous pouvez faire dans le visualiseur d'algorithmes.

Implémentation en Python

La version propre et prête pour l'entretien utilise heapq de Python comme file de priorité. Le graphe est une liste d'adjacence associant chaque nœud à une liste de paires (voisin, poids).

import heapq

def dijkstra(graph, start):
    # Chaque nœud commence infiniment loin, sauf la source.
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distance jusqu'ici, nœud)

    while pq:
        dist, node = heapq.heappop(pq)

        # Une entrée périmée et plus longue pour un nœud déjà réglé : on l'ignore.
        if dist > distances[node]:
            continue

        for neighbour, weight in graph[node]:
            new_dist = dist + weight
            # Relaxation : on a trouvé un chemin moins cher vers le voisin.
            if new_dist < distances[neighbour]:
                distances[neighbour] = new_dist
                heapq.heappush(pq, (new_dist, neighbour))

    return distances

Deux détails comptent. D'abord, nous insérons une nouvelle entrée au lieu de mettre à jour le tas sur place, puis nous ignorons les entrées périmées grâce au test dist > distances[node]. Cette "suppression paresseuse" garde le code simple et c'est une pratique courante. Ensuite, l'algorithme calcule naturellement les distances vers tous les nœuds ; pour vous arrêter tôt sur une seule cible, retournez dès que vous la retirez.

Complexité en Temps et en Espace

Le coût dépend de la file de priorité. Chaque arête peut déclencher au plus une insertion, et chaque insertion ou retrait sur un tas binaire coûte O(log V).

L'espace est O(V) pour la table des distances plus la file. Pour le raisonnement derrière ces bornes et leur comparaison sur l'ensemble des algorithmes de graphes, voir le guide de la complexité des algorithmes de graphes et l'aide-mémoire d'une page.

Quand Dijkstra échoue : les Poids Négatifs

La garantie gloutonne repose entièrement sur des poids non négatifs. Ajoutez une arête négative et tout peut casser.

Supposons que l'algorithme fige un nœud parce qu'il semble le plus proche, distance 5. Plus tard, il découvre une route d'apparence plus longue qui passe par une arête -4 et atteint en fait ce nœud en 3. Trop tard : Dijkstra a déjà déclaré 5 définitif et est passé à autre chose. La réponse est fausse.

Règle à retenir : poids non négatifs, utilisez Dijkstra. Le moindre poids négatif, utilisez Bellman-Ford, qui relâche chaque arête à répétition et peut aussi détecter les cycles négatifs.

Dijkstra face aux Autres Algorithmes

Dijkstra n'est qu'un outil parmi d'autres. Choisir le bon dépend du graphe.

Le parent le plus proche est la recherche A*, c'est-à-dire Dijkstra plus une heuristique qui oriente la recherche vers un but unique. Et Dijkstra lui-même n'est en réalité que le parcours en largeur, une simple file étant remplacée par une file de priorité.

Applications Concrètes

• Navigation et cartes : l'itinéraire le plus court ou le plus rapide entre deux lieux, l'usage classique.
• Routage réseau : les protocoles à état de liens comme OSPF utilisent Dijkstra pour calculer les tables de transfert.
• Jeux et robotique : les coûts de déplacement sur une carte, souvent avec A* par-dessus.
• Opérations et logistique : les chemins de moindre coût dans les réseaux d'approvisionnement, de télécoms et de transport, un pilier de la recherche opérationnelle.