les applications de l’algorithme de Dijkstra
• Dans routage IP :
Dijkstra, essentiel en routage IP, calcule les chemins les plus courts
entre routeurs, optimisant ainsi le transfert de paquets. Dans les
réseaux OSPF.
• Dans les services de cartographie numérique :L’algorithme de
Dijkstra peut être utilisé pour déterminer les itinéraires les plus
courts entre deux points.
• Dans le domaine de la robotique : Certains robots mobiles
utilisent l’algorithme de Dijkstra pour planifier des trajectoires
optimales.
les applications de l’algorithme de Dijkstra
• Dans les systèmes de recommandation :
peut utilisé l’algorithme de Dijkstra pour trouver
le chemin le plus court entre des utilisateurs ou des
éléments similaires dans un réseau de relations.
• Dans l’optimisation de la logistique :
• ....
Les limites de l’algorithme de Dijkstra
• La gestion des poids négatifs : pas adapté aux graphes contenant des poids d’arêtes
négatifs.
• La gestion des graphes dynamiques :nécessite de recalculer fréquemment les plus courts
chemins en raison des changements réguliers des poids des arêtes. L'algorithme de Dijkstra
est peu adapté à ce contexte, car il se limite au calcul des chemins à partir d'un seul nœud.
• Probleme d’espace mémoire : Cet algorithme consomme beaucoup de mémoire, surtout
pour les grands graphes, car il doit stocker les distances de chaque nœud.
• Complexité élevée pour des grands graphes :Bien que l’algorithme soit efficace pour des
graphes de taille modérée, sa complexité peut devenir un problème pour des graphes très
grands. La complexité en temps est de (O(V^2)) pour une implémentation simple, et de
(O((V + E) \log
autres algorithmes
Il y a beaucoup d’algorithmes pour trouver le plus court
chemin dans un graphe :
• Algorithme de Bellman-Ford.
• Algorithme de Floyd-Warshall.
• Algorithme de Johnson.
• Algorithme A*
• ...
Comparaison avec d'autres algorithmes
• Dijkstra vs Bellman-Ford
Comparaison avec d'autres algorithmes
• Dijkstra vs Floyd-Warshall
Résumé des points forts et des limites de
Dijkstra
Avantage :
Optimal pour des graphes pondérés avec des poids positifs.
Relativement efficace avec un tas binaire ou Fibonacci.
• Convient bien pour des problèmes pratiques comme la navigation (GPS.(
• Inconvénients:
• Ne fonctionne pas avec des poids négatifs.
• Moins efficace sur des graphes denses ou très grands comparés à certains algorithmes
spécialisés.