Algorithme de Dijkstra avec file de priorité

L’algorithme de Dijkstra trouve le plus court chemin depuis un nœud source unique vers tous les autres nœuds d’un graphe pondéré dont les poids d’arêtes sont non négatifs. Il fonctionne en traitant gloutonnement les nœuds dans l’ordre de leur meilleure distance connue — en développant toujours le nœud non visité le plus proche. La structure de données clé est un tas min (file de priorité), qui récupère efficacement le nœud dont la distance est la plus petite.

Algorithme de Dijkstra : (1) initialisez dist[source] = 0 et dist[all others] = inf. (2) Ajoutez (0, source) à un tas min. (3) Retirez le nœud u dont la distance est la plus petite. S’il a déjà été visité avec une distance inférieure, ignorez-le. (4) Pour chaque voisin v de u : si dist[u] + weight(u,v) < dist[v], mettez à jour dist[v] et ajoutez (dist[v], v) au tas. (5) Répétez jusqu’à ce que le tas soit vide.

Le module Python heapq implémente un tas min. Nous représentons le graphe sous forme de liste d’adjacence : graph[u] = [(v, weight), ...]. Le tas stocke des tuples (distance, node). Nous utilisons un ensemble visited pour ignorer les entrées obsolètes du tas — celles qui ont été ajoutées avant la découverte d’un meilleur chemin.

Considérez un graphe de 5 nœuds et les arêtes suivantes : 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). Les plus courts chemins depuis le nœud 0 sont les suivants : vers 1 en passant par 0→2→1, avec un coût de 3 ; vers 2, avec un coût de 1 ; vers 3 en passant par 0→2→1→3, avec un coût de 4 ; vers 4 en passant par 0→2→1→3→4, avec un coût de 7. Dijkstra trouve tous ces chemins en un seul parcours, et pas uniquement le chemin vers une cible donnée.

La validité de Dijkstra repose sur le fait qu'une fois qu'un nœud est retiré du tas min, sa distance est définitive. Cela n'est vrai que si les poids des arêtes sont non négatifs. Avec une arête négative u→v de poids -5, après avoir visité v, nous pourrions trouver un chemin passant par u qui est plus court — mais v est déjà marqué comme visité. Une seule arête négative peut invalider tous les calculs de distance ultérieurs.

Ce problème ajoute une contrainte : au plus k escales. La version standard de Dijkstra ne gère pas nativement le nombre d'étapes. Solution : étendre l'état à (cost, node, stops_remaining). Utilisez Dijkstra avec ce triplet, ou utilisez Bellman-Ford avec k+1 passes de relaxation. La version modifiée de Dijkstra s'arrête lorsque stops_remaining atteint 0, ce qui empêche les sauts supplémentaires.

Avec un tas binaire, Dijkstra s'exécute en O((V + E) log V) : chaque sommet est retiré une fois (V retraits), chaque arête peut déclencher une insertion (E insertions), et chaque opération sur le tas coûte O(log V). Avec un tas de Fibonacci, la borne s'améliore pour atteindre O(E + V log V), mais le module de tas binaire de Python est utilisé. Pour les graphes creux (E ≈ V), la version avec tas binaire est en O(V log V) ; pour les graphes denses (E ≈ V²), elle est en O(V² log V).

Pour récupérer le chemin réel (et pas seulement les distances), maintenez un tableau prev : lors de la mise à jour de dist[v], définissez prev[v] = u. Une fois l'algorithme terminé, reconstituez le chemin de la source à la destination en remontant les pointeurs : commencez à dst, suivez les pointeurs prev jusqu'à source, puis inversez le résultat.

Lorsque les nœuds sont des chaînes ou des entiers non contigus, utilisez un defaultdict(list) pour la liste d'adjacence et un dict classique pour les distances. C'est fréquent dans les problèmes de LeetCode, comme celui du délai de propagation du réseau, où les nœuds sont numérotés de 1 à n. Pensez à utiliser dist = {node: inf for node in all_nodes} et à vérifier les nœuds inaccessibles après l'algorithme.

Pour les graphes non pondérés, BFS trouve les plus courts chemins en O(V + E) — plus rapidement que Dijkstra, en O((V+E) log V). Dijkstra généralise BFS aux graphes pondérés en utilisant une file de priorité plutôt qu'une file FIFO classique. Lorsque tous les poids des arêtes sont égaux, Dijkstra se réduit à BFS. Choisissez BFS pour les graphes non pondérés, Dijkstra pour les poids non négatifs et Bellman-Ford pour les poids négatifs.

La version théorique de Dijkstra utilise une file de priorité avec une opération de décrémentation de clé : lorsqu'une distance de nœud s'améliore, mettez sa priorité à jour directement. Cela nécessite un tas de Fibonacci pour obtenir O(E + V log V), mais cette structure est difficile à implémenter. L'approche par suppression différée utilisée lors des entretiens consiste plutôt à insérer une nouvelle entrée et à ignorer les retraits obsolètes — elle est plus simple, avec seulement un surcoût constant. En Python, la suppression différée avec un tas binaire est l'implémentation standard pour les entretiens.

Vérifiez votre compréhension des concepts de Structures de données et algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.

Dans cette leçon, vous avez appris que Dijkstra utilise un tas min pour traiter gloutonnement les nœuds dans l'ordre de leur meilleure distance actuelle, qu'il s'exécute en O((V+E) log V) et échoue avec les arêtes de poids négatif, et que les entrées obsolètes du tas sont gérées en vérifiant un ensemble de nœuds visités lors du retrait. Ensuite, nous étudierons Bellman-Ford, qui gère les poids négatifs grâce à n-1 passes de relaxation.