Algorithme de chemin le plus court de Dijkstra

Plus courts chemins

Dans de nombreux contextes (réseaux routiers, télécommunications, planification, IA…), on modélise une situation par :

• un graphe pondéré
• où chaque arête possède un coût (distance, temps, énergie, pénalité…)

Cadre mathématique

Graphe pondéré

On considère un graphe : \[ G = (S, A, w) \] où :

• \(S\) : ensemble des sommets
• \(A\) : ensemble des arêtes
• \(w : A \to \mathbb{R}\) : fonction de poids (coût)

Longueur d'un chemin

Soit un chemin : \[ P = (v_0, v_1, \dots, v_k) \] Sa longueur est : \[ \ell(P) = \sum_{i=0}^{k-1} w(v_i, v_{i+1}) \] Un plus court chemin est un chemin de longueur minimale parmi tous les chemins possibles.

Algorithme de Dijkstra

L'algorithme a été conçu par Edsger W. Dijkstra en 1956 et publié en 1959. Dans sa lettre originale, il décrit sa découverte comme une solution "en 20 minutes" à un problème posé par un mathématicien non informaticien. La simplicité de sa formulation cache une profondeur conceptuelle qui en fait l'un des joyaux de l'algorithmique des graphes.

Dijkstra est la généralisation naturelle du BFS :

• BFS → graphes non pondérés
• Dijkstra → graphes pondérés à poids positifs

Il constitue l'algorithme de référence pour le calcul des plus courts chemins depuis une source unique.

Cadre formel

On considère :

• un graphe pondéré \(G = (S, A, w)\)
• une source \(s \in S\)

L'Hypothèse Fondamentale

Objectif mathématique

Pour tout sommet \(v \in S\), déterminer :

\[ d(v) = \min \{ \ell(P) \mid P \text{ chemin de } s \text{ à } v \} \]

où \(\ell(P)\) est la somme des poids des arêtes du chemin.

L'intuition fondamentale

L'algorithme fonctionne sur un principe glouton : il traite les sommets dans l'ordre croissant de leur distance à partir du sommet source \(s\).

Lorsqu'un sommet \(u\) est choisi comme étant celui de plus petite distance provisoire, sa distance devient définitivement optimale (on le marque comme "traité").

Pourquoi cette distance est-elle définitive ?

Cette garantie repose sur deux hypothèses clés :

1. Tous les poids des arêtes sont positifs ou nuls.
2. Aucun chemin alternatif plus long ne pourra venir améliorer cette distance plus tard.
   En effet, puisque tous les chemins non encore explorés depuis \(s\) vers \(u\) devront passer par des sommets encore non traités (donc de distance au moins égale à celle de \(u\)), et que toutes les arêtes ont un poids positif, leur coût total ne pourra qu'être supérieur ou égal.

Structures de données maintenues

Un algorithme efficace est indissociable des structures de données qui soutiennent son exécution. Dijkstra maintient un état cohérent à travers trois informations fondamentales.

Le registre des distances : \(d[v]\)

Pour chaque sommet \(v\), l'algorithme conserve une estimation de la meilleure distance connue depuis la source.

Initialisation :

\[ \begin{cases} d[s] = 0 & \text{(la source est à distance nulle d'elle-même)} \\ d[v] = +\infty & \forall v \neq s \text{ (inconnu initialement)} \end{cases} \]

L'ensemble des certitudes : \(F\)

La mémoire des parcours : \(\pi[v]\)

Initialisation :

\[ \pi[v] = \text{None}, \text{ pour tout } v \in S \]

L'opération fondamentale : la relaxation d'une arête

La relaxation opère comme un resserrement d'une borne supérieure : elle rapproche l'estimation \(d[v]\) de sa valeur optimale. Chaque relaxation abaisse potentiellement \(d[v]\), la faisant converger vers la vraie distance minimale.

L'algorithme pas à pas

Étape 0 : Initialisation

On prépare le terrain en fixant la distance de la source à 0 et toutes les autres à l'infini. Aucun sommet n'est considéré comme traité.

Étape 1 : Sélection (Le choix glouton)

Parmi tous les sommets non traités (\(v \notin F\)), on choisit celui qui possède la plus petite distance provisoire \(d(v)\) : \[ u = \arg \min_{v\notin F} d(v) \] Ce sommet \(u\) entre alors dans l'ensemble \(F\). Sa distance est désormais définitive.

Étape 2 : Mise à jour (Relaxation)

Pour chaque voisin \(v\) du sommet \(u\) que l'on vient de sélectionner, on tente de relaxer l'arête \((u,v)\).

Étape 3 : Itération

On répète les étapes 1 et 2 jusqu'à ce que :

1. Tous les sommets accessibles soient dans \(F\).
2. Ou, si l'on cherche un trajet vers une cible précise, que cette cible soit ajoutée à \(F\).

Algorithme de Dijkstra

Pour tout sommet v Faire
    d[v] ← +∞
    π[v] ← None
FinPour
d[s] ← 0
F ← ∅

TantQue F ≠ S Faire
    u ← sommet de {S\F} avec d[u] minimal
    ajouter u à F

    Pour chaque voisin v ∉ F de u Faire
        Si d[v] > d[u] + w(u,v) Alors
            d[v] ← d[u] + w(u,v)
            π[v] ← u
        FinSi
    FinPour
FinTantQue

Exemple

On considère le graphe suivant et on effectue l'algorithme de Dijkstra à partir du sommet A.

Étape 0 : Initialisation

On part de \(A\). Sa distance est \(0\), toutes les autres sont à l'infini.

• \(d(A)=0\)
• \(d(B) = d(C) = d(D) = d(E) = d(F) = d(G) = +\infty\)
• Ensemble des sommets validés \(F=\varnothing\)

Étape 1 : Depuis A

On regarde les voisins directs de \(A\) : \(B, C\) et \(D\).

• \(d(B) = d(A) + 3 = 0 + 3 = 3\)
• \(d(C) = d(A) + 4 = 0 + 4 = 4\)
• \(d(D) = d(A) + 1 = 0 + 1 = 1\)

Le minimum entre \(B:3, C:4, D:1\) est \(D\). On verrouille \(D\).

Étape 2 : Depuis D

On regarde les voisins de \(D\) : \(B, E, F\) et \(G\). On additionne leur poids à la distance de \(D\) \(d(D) = 1\).

• \(d(B) = d(D) + 13 = 1 + 13 = 14\) (On garde \(3\) car \(3<14\))
• \(d(E) = d(D) + 10 = 1 + 10 = 11\)
• \(d(F) = d(D) + 7 = 1 + 7 = 8\)
• \(d(G) = d(D) + 11 = 1 + 11 = 12\)

Le minimum parmi les non-traités \(B:3, C:4, E:11, F:8, G:12\) est \(B\). On verrouille \(B\).

Étape 3 : Depuis B

Le seul voisin sortant de \(B\) est \(E\).

• \(d(E) = d(B) + 6 = 3 + 6 = 9\) (On remplace 11 par 9 car c'est plus court)

Le minimum parmi \(C:4, E:9, F:8, G:12\) est \(C\). On verrouille \(C\).

Étape 4 : Depuis C

Voisins de \(C\) : \(D\) (déjà verrouillé) et \(F\).

• \(d(F) = d(C) + 2 = 4 + 2 = 6\) (On remplace 8 par 6 car c'est plus court)

Le minimum parmi \(E:9, F:6, G:12\) est \(F\). On verrouille \(F\).

Étape 5 : Depuis F

Le seul voisin sortant de \(F\) est \(G\).

• \(d(G) = d(F) + 8 = 6 + 8 = 14\) (On garde \(12\) car \(12<14\))

Le minimum restant est \(E\) (distance 9). On verrouille \(E\).

Étape 6 : Depuis E

Le seul voisin sortant de \(E\) est \(G\).

• \(d(G) = d(E) + 1 = 9 + 1 = 10\) (On remplace 12 par 10 car c'est plus court)

Il ne reste que \(G\). On le verrouille à \(10\).

Étape 7 : Depuis G (la fin)

Le sommet G n'a pas de voisins.

Distances minimales depuis A :

• \(d(A) = 0\)
• \(d(D) = 1\)
• \(d(B) = 3\)
• \(d(C) = 4\)
• \(d(F) = 6\)
• \(d(E) = 9\)
• \(d(G) = 10\)

Chemins optimaux (en remontant les prédécesseurs) :

• Pour aller à \(G\) : \(A\rightarrow B\rightarrow E\rightarrow G\) (Poids : \(3+6+1=10\))
• Pour aller à \(F\) : \(A\rightarrow C\rightarrow F\) (Poids : \(4+2=6\))
• Pour aller à \(E\) : \(A\rightarrow B\rightarrow E\) (Poids : \(3+6=9\))

Implémentation Python

On suppose le graphe stocké sous forme de liste d'adjacence :

\[ adj[u] = [(v_1, w_1), (v_2, w_2), \dots] \]

C'est la représentation standard (efficace et naturelle).

Quel que soit le langage ou la structure utilisée, Dijkstra fait toujours la même chose :

1. Maintenir une distance provisoire d(v) pour chaque sommet
2. Répéter :
   • choisir le sommet non traité de distance minimale
   • le rendre définitif
   • relaxer ses arêtes

L'implémentation naïve (Avec les listes)

Au cœur de chaque itération, l'algorithme doit identifier le prochain nœud à traiter. Le processus se décompose ainsi :

1. Maintenir une liste dist contenant les distances actuelles.
2. Parcourir l'intégralité des sommets n'appartenant pas encore à l'ensemble des sommets visités \(F\).
3. Extraire le sommet \(v\) tel que : \(\min\{d(v) | v \notin F\}\)

L'efficacité de cette méthode est dictée par deux facteurs cumulatifs :

• La recherche du minimum : Pour chaque sélection, le parcours de tous les sommets non visités engendre un coût de \(O(|S|)\).
• La répétition du cycle : Cette opération est répétée pour chacun des \(|S|\) sommets du graphe.

En conséquence, la complexité globale de cette version naïve s'élève à \(O(|S|^2)\).

Extraire le minimum

def extraire_min(dist, F):
    n = len(dist)
    
    u_min = None
    dist_min = float('inf')
    
    for i in range(n):
        # On cherche le sommet non visité avec la plus petite distance actuelle
        if i not in F and dist[i] < dist_min:
            dist_min = dist[i]
            u_min = i
    return u_min

Dijkstra

def dijkstra_liste(adj, source):
    n = len(adj)
    # Initialisation : tous les sommets sont à une distance infinie
    dist = [float('inf')] * n
    # Tableau des pères pour reconstruire les chemins
    pred = [None] * n
    # Ensemble des sommets déjà fixés (visités)
    F = set()

    # La distance de la source à elle-même est nulle
    dist[source] = 0

    # On doit traiter les n sommets du graphe
    for _ in range(n):
        # 1. SÉLECTION : On choisit le sommet le plus "proche" non encore traité
        u = extraire_min(dist, F)

        # Si extraire_min renvoie None, les sommets restants sont inaccessibles
        if u is None:
            break

        # On ajoute le sommet u à l'ensemble des sommets fixés
        F.add(u)

        # 2. RELAXATION : Mise à jour des distances des voisins de u
        for v, w in adj[u]:
            # Si passer par u offre un chemin plus court vers v
            if v not in F and dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                pred[v] = u

    return dist, pred

Exemple

# A=0, B=1, C=2, D=3, E=4, F=5, G=6.
graphe = [
    [(1, 3), (2, 4), (3, 1)], # A
    [(4, 6)],                 # B
    [(3, 9), (5, 2)],         # C
    [(5, 7), (4, 10), (1, 13), (6, 11)], # D
    [(6, 1)],                 # E
    [(6, 8)],                 # F
    []                        # G
]

distances, peres = dijkstra_liste(graphe, 0)
print("Distances =", distances)

Distances = [0, 3, 4, 1, 9, 6, 10]
Précédences = [None, 0, 0, 0, 1, 2, 4]

Distances minimales depuis A :

• \(d(A) = 0\)
• \(d(B) = 3\)
• \(d(C) = 4\)
• \(d(D) = 1\)
• \(d(E) = 9\)
• \(d(F) = 6\)
• \(d(G) = 10\)

L'implémentation améliorée (Avec la file de priorité)

Comme vu au chapitre "Les arbres binaires", une file de priorité (particulièrement un tas min) est précisément conçue pour ce type de problème. Son interface offre deux opérations critiques :

• Extraction du minimum : Au lieu de parcourir tous les sommets, on retire directement la racine du tas en \(O(\log|S|)\).
• Mise à jour (Insertion/Relâchement) : Lorsqu'une distance est améliorée (relaxation), on réorganise la structure en \(O(\log|S|)\).

Analyse de complexité

Chaque sommet du graphe est extrait de la file de priorité exactement une fois.

• Nombre d'opérations : \(|S|\) extractions.
• Coût d'une extraction : Dans un tas binaire, l'opération extract-min coûte \(O(\log|S|)\).

\[ O(|S|\times \log|S|) \]

À chaque fois qu'un arc \((u,v)\) est relâché et qu'une distance est améliorée, nous devons mettre à jour la priorité du sommet \(v\) dans le tas (ou insérer une nouvelle entrée).

• Nombre d'opérations : Dans le pire des cas, chaque arc est examiné une fois. Il y a donc au maximum \(|A|\) relaxations.
• Coût d'une mise à jour/insertion : L'insertion ou la réorganisation d'un élément dans un tas binaire coûte \(O(\log|S|)\).

\[ O(|A|\times \log|S|) \]

En additionnant ces deux contributions, on obtient la complexité globale :

\[ T = O((|S| + |A|) \times \log|S|) \]

Extraire le minimum avec tas

import heapq

def extraire_min_tas(file_priorite):
    # heapq.heappop renvoie le plus petit élément (distance, sommet)
    return heapq.heappop(file_priorite)

Dijkstra avec Tas

def dijkstra_tas(adj, source):
    n = len(adj)
    dist = [float('inf')] * n
    pred = [None] * n
    # Contrairement à la version liste, on utilise un ensemble pour 
    # marquer les sommets dont la distance est définitivement fixée.
    F = set()

    dist[source] = 0
    
    # La file de priorité contient des couples (distance, sommet)
    # On commence par y insérer la source
    file_priorite = [(0, source)]

    while file_priorite:
        # 1. SÉLECTION : O(log S) au lieu de O(S)
        d_u, u = extraire_min_tas(file_priorite)

        # Si le sommet a déjà été traité, on l'ignore 
        # (nécessaire car heapq ne gère pas nativement la mise à jour de priorité)
        if u in F:
            continue
        
        F.add(u)

        # 2. RELAXATION : O(log V) par arc au lieu de O(1)
        for v, w in adj[u]:
            if v not in F and dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                pred[v] = u
                # On insère la nouvelle distance dans le tas
                heapq.heappush(file_priorite, (dist[v], v))

    return dist, pred

Exemple

distances, peres = dijkstra_tas(graphe, 0)
print("Distances =", distances)

Distances = [0, 3, 4, 1, 9, 6, 10]
Précédences = [None, 0, 0, 0, 1, 2, 4]

Les limites de Dijkstra

L'algorithme de Dijkstra est dit "aveugle". Pour trouver le chemin vers une cible spécifique, il explore les sommets par cercles concentriques de distance croissante depuis la source.

• Neutralité spatiale : Dijkstra ne sait pas où se trouve la cible. Il explore aussi bien vers le Nord que vers le Sud, même si la cible est manifestement à l'Est.
• Inefficacité relative : Dans un graphe de grande taille (comme une carte routière), il finit par traiter une quantité massive de sommets totalement non pertinents.