Öncelikli kuyruk
- Algoritmalar kursu
- İleri seviye
- Ders 30/56
- 4 dk
Dijkstra'nın öncelikli kuyrukla verimli çalıştığını öğrenirsin.
Öncelikli kuyruk
Dijkstra, her adımda en küçük mesafeye sahip ziyaret edilmemiş düğümü seçer. Bu seçim, öncelikli kuyrukla hızlanır.
Basit uygulamada doğrusal arama da yeterlidir: tüm ziyaret edilmemiş düğüümü tarayıp en küçük dist'i buluruz.
Başlangıç durumu
Tüm düğümlerin mesafesi inf olarak başlatılır, yalnızca dist[src] = 0 olur. Ziyaret dizisi False ile dolar.
Bu başlangıç durumu, algoritmanın tek kaynaktan adım adım yayılmasını sağlar.
Uygulama init_dist fonksiyonu
init_dist(n, src) yaz. float('inf') ile dolu dizi döndür, dist[src] = 0 yap. print(init_dist(4, 0)) ile yazdır.
Başlangıç kodu
def init_dist(n, src):
# Başlangıç mesafe dizisini döndürÖrnek çözüm
def init_dist(n, src):
# Başlangıç mesafe dizisini döndür
dist = [float('inf')] * n
dist[src] = 0
return dist
print(init_dist(4, 0))Beklenen çıktı
[0, inf, inf, inf]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 başlangıç mesafesi
dist[src] = ____dist[src] = 0Açıklama: 0 doğru.
2 Başlangıçta dist[src] kaç olur?
- inf
- 0 Doğru cevap
- 1
- -1
Açıklama: dist[src] = 0 başlangıç değeridir.
3 Öncelikli kuyruk: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
dist[src] |
0 |
dist[i] |
inf |
visited |
False |
n |
Düğüm sayısı |