Time and Space Complexity
Leçon 7 sur 9 du cours Algorithme de Dijkstra - Algorithmes de graphes de Coddy.
Complexité temporelle :
- O(V2 + V*E) tel qu'écrit ici (chacun des V rounds parcourt les sommets pour trouver le minimum et parcourt les arêtes pour les relâcher). Avec un tas binaire et une liste d'adjacence, cela s'améliore en O((V + E) log V).
Complexité spatiale :
- O(V) pour les tableaux de distance et de visite (plus les arêtes d'entrée).
Résumé :
- Dijkstra trouve les distances les plus courtes à source unique pour les poids non négatifs en finalisant de manière gloutonne le sommet le plus proche et en relâchant ses arêtes.
- Il ne fonctionne pas avec des arêtes négatives ; utilisez Bellman-Ford pour celles-ci.
Essayez vous-même
Cette leçon ne comprend pas de défi de code.
Testez-vousCette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.
Toutes les leçons de Algorithme de Dijkstra - Algorithmes de graphes
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity