Algorithme de Dijkstra
- Introduite par
- Edsger W. Dijkstra
- Année
- 1956
- Type
- algorithm
- Famille
- Graph Algorithms
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
L'algorithme de Dijkstra, introduit par Edsger W. Dijkstra en 1956, est l'un des algorithmes les plus fondamentaux en informatique pour résoudre le problème du plus court chemin à source unique.
Il trouve le chemin le plus court d'un sommet de départ vers tous les autres sommets dans un graphe pondéré avec des poids d'arête non négatifs.
L’intuition derrière la méthode
L'algorithme maintient un ensemble de sommets dont les distances les plus courtes depuis la source sont déjà connues, et étend itérativement cet ensemble en sélectionnant le sommet non traité le plus proche et en mettant à jour les distances de ses voisins. L'idée clé est la propriété gloutonne : une fois qu'un sommet est sélectionné, sa distance depuis la source est définitive car tous les poids d'arête sont non négatifs, donc tout chemin plus long passant par des sommets non visités ne peut pas être plus court. Ceci garantit la correction et l'optimalité.
Histoire
Edsger W. Dijkstra a publié son algorithme en 1959 dans un article de trois pages qui deviendrait l'une des œuvres les plus citées en informatique. L'algorithme est issu du travail de Dijkstra sur l'ordinateur ARMAC à Amsterdam. Au fil des décennies, de nombreuses améliorations ont été apportées, notamment de meilleures structures de données (les tas de Fibonacci atteignant une complexité O(E+VlogV)) et des variantes bidirectionnelles. L'algorithme reste central pour les protocoles de routage modernes comme OSPF dans les réseaux.
Quand l’utiliser
Appliquer l'algorithme de Dijkstra lors de la recherche des plus courts chemins dans des graphes avec des poids d'arête non négatifs. Il est idéal pour les systèmes de navigation, le routage réseau et tout problème de graphe nécessitant des chemins optimaux. Utilisez-le pour les plus courts chemins à source unique vers tous les sommets. Pour les graphes avec des poids négatifs, utilisez Bellman-Ford à la place. Pour une recherche bidirectionnelle ou une guidage heuristique, considérez l'algorithme A*.
Limites et points d’attention
- Ne peut pas gérer les graphes avec des poids d'arête négatifs
- Calcule les plus courts chemins vers tous les sommets, pas seulement une destination (bien qu'il puisse se terminer plus tôt)
- Moins efficace que A* lorsque des informations heuristiques sont disponibles
- Nécessite que tous les sommets soient découverts ; inefficace pour une connectivité très éparse
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Simple à comprendre et à implémenter avec des garanties de correction claires
- Efficace avec des structures de données appropriées : O((V+E)logV) avec tas binaire, O(V²) avec tableau
- Optimal pour les graphes à poids non négatifs ; prouve l'optimalité des chemins calculés
- Fonctionne sur les graphes dirigés et non dirigés
- Fondation pour de nombreuses extensions et algorithmes apparentés
Applications
- Systèmes GPS et de navigation : recherche des itinéraires les plus courts pour les véhicules et les piétons
- Protocoles de routage réseau : détermination des chemins optimaux pour les paquets de données dans les réseaux informatiques
- Réseaux sociaux : recherche des chemins de connexion les plus courts entre utilisateurs ou influenceurs
- Développement de jeux : recherche de chemin pour l'intelligence artificielle et le mouvement des personnages non-joueurs
- Planification de mouvement robotique : calcul des trajectoires optimales pour les systèmes robotiques
- Télécommunications : optimisation du routage des appels et des chemins de propagation des signaux
Comment ça marche
Comment ça marche
Définir la distance de la source à zéro et toutes les autres distances à l'infini. Marquer tous les sommets comme non visités et créer une file de priorité.
Sélectionner le sommet non visité avec la distance minimale depuis la source en utilisant la file de priorité.
Pour chaque voisin du sommet sélectionné, si le chemin passant par le sommet sélectionné offre une distance plus courte, mettre à jour la distance du voisin et l'ajouter à la file de priorité.
Pièges courants
- Utilisation de l'algorithme sur des graphes avec des poids négatifs, résultant en des chemins les plus courts incorrects
- Implémentation inefficace avec une opération d'extraction minimale en temps linéaire, entraînant de mauvaises performances
- Oubli de mettre à jour correctement les distances lorsque les voisins sont revisités par des chemins différents
Questions fréquentes
Pourquoi l'algorithme de Dijkstra échoue-t-il sur les poids négatifs ?
L'algorithme suppose qu'une fois qu'un sommet est finalisé, aucun chemin plus court ne peut être trouvé via des sommets non visités. Avec des poids négatifs, un chemin plus long pourrait plus tard s'améliorer lorsqu'une arête négative est utilisée, violant cette hypothèse.
Quelle structure de données doit être utilisée pour la file de priorité ?
Les tas binaires fournissent des opérations O(logV) pour l'insertion et l'extraction, résultant en une complexité totale O((V+E)logV). Les tas de Fibonacci atteignent O(E+VlogV) mais ont de grands facteurs constants. Les tableaux fonctionnent bien pour les petits graphes.
Comment l'algorithme de Dijkstra peut-il trouver le chemin vers une destination spécifique ?
Terminez l'algorithme dès que le sommet de destination est sélectionné (sa distance est finalisée), en évitant les calculs inutiles. Alternativement, reconstruisez le chemin en maintenant des pointeurs parents pendant l'exécution.
L'algorithme de Dijkstra peut-il être utilisé dans des graphes non dirigés ?
Oui, les graphes non dirigés peuvent être représentés comme des graphes dirigés avec des arêtes dans les deux sens pour chaque arête non dirigée, chacune avec le même poids. L'algorithme fonctionne de manière identique sur la représentation bidirectionnelle.
Méthodes associées
Sources
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
Ouvrir la référence DOICopié.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN : 978-0-262-03384-8Copié.