Dijkstra avec File de Priorité

1. Le Problème du Plus Court Chemin et l'Approche Gloutonne

Le problème que nous abordons est celui du plus court chemin à origine unique (Single-Source Shortest Path, SSSP).

Formellement, étant donné un graphe orienté et pondéré $G=(V,A)$, une fonction de poids $w:A\to {\mathbb{R}}_0^{+}$ qui associe un poids non-négatif à chaque arc, et un sommet source $s\in V$, l'objectif est de trouver, pour chaque sommet $v\in V$, la longueur du plus court chemin de $s$ à $v$. Nous notons cette longueur $\delta (s,v)$.

Pour ce faire, l'algorithme de Dijkstra maintient pour chaque sommet $v$ :

• d[v]: une estimation (un majorant) de $\delta (s,v)$. Initialement, d[s] = 0 et d[v] = ∞ pour tout $v\ne s$.
• π[v]: le prédécesseur de $v$ dans le chemin de s à v actuellement connu comme étant le plus court.

L'opération fondamentale de l'algorithme est le relâchement (relaxation). Pour un arc $(u,v)$ de poids $w(u,v)$, relâcher cet arc consiste à vérifier si passer par $u$ offre un meilleur chemin vers $v$ que celui connu jusqu'à présent.

Relâcher(u, v, w):
Si d[v] > d[u] + w(u, v) alors
    d[v] ← d[u] + w(u, v)
    π[v] ← u

L'algorithme de Dijkstra est un algorithme glouton. À chaque étape, il sélectionne le sommet $u$ non encore "finalisé" qui a la plus petite estimation de distance d[u], considère que cette estimation est désormais la distance définitive, et relâche tous les arcs qui partent de $u$.

Le document suivant, issu d'une préparation à l'Agrégation, formalise ces notions.

2. Mécanique de l'Algorithme de Dijkstra

L'algorithme de Dijkstra maintient un ensemble de sommets dont la distance la plus courte depuis la source a été finalisée. À chaque étape :

1. Il extrait le sommet u qui n'est pas encore finalisé et qui possède la plus petite valeur d[u].
2. Il ajoute u à l'ensemble des sommets finalisés.
3. Pour chaque voisin v de u, il effectue l'opération de relâchement Relâcher(u, v, w).

Ce processus continue jusqu'à ce que tous les sommets accessibles aient été finalisés. La vidéo suivante illustre ce mécanisme de manière très claire, étape par étape.

La question cruciale pour une implémentation efficace est : comment trouver rapidement, à chaque étape, le sommet non finalisé avec la plus petite distance ? Un balayage de tous les sommets serait en $\mathcal{O}(|V|)$, menant à une complexité totale de $\mathcal{O}(|V{|}^2)$. Nous pouvons faire mieux.

3. Le Rôle Central de la File de Priorité

C'est ici qu'intervient la file de priorité (priority queue), généralement implémentée par un tas min (min-heap). Cette structure de données est conçue pour stocker des éléments et en extraire efficacement celui qui a la plus petite "priorité" (ici, la plus petite distance d[u]).

L'algorithme s'articule ainsi :

1. Initialiser les distances et les prédécesseurs.
2. Insérer (0, s) dans une file de priorité min (le couple (distance, sommet)).
3. Tant que la file de priorité n'est pas vide :
   a. Extraire le couple (dist, u) avec la plus petite distance.
   b. Si u a déjà été finalisé, l'ignorer et continuer.
   c. Marquer u comme finalisé.
   d. Pour chaque voisin v de u, relâcher l'arc (u,v). Si la distance d[v] est améliorée, insérer (d[v], v) dans la file de priorité.

La vidéo suivante explique très bien l'intérêt de cette structure.

Le pseudo-code ci-dessous formalise cette approche.

Pour tester votre compréhension du fonctionnement de la file de priorité, considérez la question suivante :

Réflexion : Au départ, la file contient (0, 0). Après avoir traité le sommet 0, on ajoute ses trois voisins (1, 4, 7). La file contient 3 éléments. Après avoir traité le sommet 4 (le plus proche), on ajoute son voisin 5... Continuez le raisonnement. Le nombre maximal d'éléments dans la file sera 4.

4. Implémentation en Python avec heapq

Passons à la mise en œuvre. En Python, le module heapq fournit une implémentation efficace des tas. Il est essentiel de le maîtriser.

L'article ci-dessous est une ressource exceptionnelle. Il fournit une implémentation Python propre et idiomatique, l'explique ligne par ligne, et analyse sa complexité.

Voici le cœur de l'implémentation, inspiré de la ressource :

import heapq

def dijkstra(graph, start_node):



    # graph: dictionnaire {node: [(neighbor, weight), ...]}
    



    # 1. Initialisation
    distances = {node: float('inf') for node in graph}
    distances[start_node] = 0
    



    # File de priorité : stocke des tuples (distance, node)
    priority_queue = [(0, start_node)]
    



    # 2. Boucle principale
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        



        # Ignorer si on a déjà trouvé un chemin plus court
        if current_distance > distances[current_node]:
            continue
            



        # 3. Relaxation des voisins
        for neighbor, weight in graph.get(current_node, []):
            distance = current_distance + weight
            



            # Si un meilleur chemin est trouvé
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
                
    return distances

5. Complexité et Limites

• Complexité temporelle : Avec une file de priorité implémentée par un tas binaire, chaque insertion (heappush) et extraction du minimum (heappop) prend un temps en $\mathcal{O}(\log |V|)$. Chaque sommet est extrait une seule fois. Chaque arc est relâché une seule fois. La complexité est donc dominée par les opérations sur le tas, menant à $\mathcal{O}((|V|+|A|)\log |V|)$. C'est une amélioration significative par rapport à $\mathcal{O}(|V{|}^2)$ pour les graphes épars (où $|A|$ est proche de $|V|$).

• Complexité spatiale : Elle est de $\mathcal{O}(|V|+|A|)$ pour stocker le graphe, le tableau des distances et la file de priorité (qui peut contenir au pire tous les sommets).

• Limite fondamentale : L'algorithme de Dijkstra ne fonctionne que si tous les poids des arcs sont non-négatifs. Le caractère glouton de l'algorithme (finaliser la distance d'un sommet de façon définitive) est mis en échec par les poids négatifs, qui pourraient révéler un chemin plus court via un sommet déjà finalisé.

Conclusion

L'algorithme de Dijkstra est une pierre angulaire de l'algorithmique des graphes, et son implémentation efficace est un savoir-faire indispensable pour l'Agrégation.

Points clés à retenir :

• Dijkstra résout le problème des plus courts chemins depuis une source unique dans un graphe à poids non-négatifs.
• Son approche est gloutonne : il finalise à chaque étape le sommet le plus proche non encore finalisé.
• L'utilisation d'une file de priorité (tas min) est essentielle pour une implémentation efficace, menant à une complexité de $\mathcal{O}((|V|+|A|)\log |V|)$.
• L'opération de relâchement est au cœur du mécanisme de mise à jour des distances.

Dans notre prochaine leçon, nous nous attaquerons à la preuve de correction de l'algorithme de Dijkstra. C'est une démonstration classique, souvent exigée, qui repose sur un raisonnement par récurrence et qui justifie formellement pourquoi l'approche gloutonne fonctionne dans le cas des poids non-négatifs.