Time and Space Complexity
Coddy'nin Dijkstra Algoritması - Graf Algoritmaları kursunda ders 7 / 9.
Zaman Karmaşıklığı:
- Burada yazıldığı gibi O(V2 + V*E) (V turun her biri, minimumu bulmak için köşeleri tarar ve gevşetmek için kenarları tarar). Bir ikili yığın (binary heap) ve bir komşuluk listesi (adjacency list) ile O((V + E) log V) değerine iyileşir.
Alan Karmaşıklığı:
- Mesafe ve visited dizileri için O(V) (artı girdi kenarları).
Özet:
- Dijkstra, en yakın köşeyi açgözlü (greedy) bir şekilde kesinleştirerek ve kenarlarını gevşeterek (relaxing) negatif olmayan ağırlıklar için tek kaynaklı en kısa mesafeleri bulur.
- Negatif kenarlarla çalışmaz; bunlar için Bellman-Ford kullanın.
Kendin dene
Bu ders bir kod alıştırması içermiyor.
Kendini test etBu ders kısa bir quiz içerir. Soruları yanıtlamak ve ilerlemeni kaydetmek için derse başla.
Dijkstra Algoritması - Graf Algoritmaları bölümündeki tüm dersler
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity