Tek kaynak
- Algoritmalar kursu
- İleri seviye
- Ders 29/56
- 4 dk
Bir kaynaktan tüm düğümlere en kısa yolu bulan algoritmayı öğrenirsin.
Tek kaynak
Dijkstra algoritması, bir graftaki tek bir başlangıç düğümünden tüm diğer düğümlere en kısa yolları bulur. Negatif olmayan ağırlıklar gerektirir.
Çıktı, bir mesafe dizisidir: dist[i] başlangıçtan i'ye en kısa mesafedir. Negatif kenar varsa algoritma çalışmaz.
Komşuluk listesi
Graf, her düğüm için bir komşu listesi olarak temsil edilir. Her eleman (neighbor, weight) çiftidir; örneğin graph[0] = [(1, 4), (2, 1)].
Bu gösterim, seyrek graflarda yer tasarrufu sağlar ve Dijkstra'nın verimli çalışmasını mümkün kılar.
Uygulama init_graph fonksiyonu
init_graph() yaz. Komşuluk listesini döndür. print(init_graph()) ile yazdır.
Başlangıç kodu
def init_graph():
# Komşuluk listesini döndürÖrnek çözüm
def init_graph():
# Komşuluk listesini döndür
return [[(1, 4), (2, 1)], [(3, 1)], [(1, 2), (3, 5)], []]
print(init_graph())Beklenen çıktı
[[(1, 4), (2, 1)], [(3, 1)], [(1, 2), (3, 5)], []]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Dijkstra hangi durumu desteklemez?
- Negatif ağırlıklar Doğru cevap
- Negatif olmayan ağırlıklar
- Sıfır ağırlıklar
- Tamsayı ağırlıklar
Açıklama: Dijkstra negatif ağırlıkları desteklemez.
2 kenar ağırlığı
graph[0] = [(1, ____)]graph[0] = [(1, 4)]Açıklama: 4 doğru.
3 Tek kaynak: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
graph[0] |
[(1,4),(2,1)] |
graph[1] |
[(3,1)] |
graph[2] |
[(1,2),(3,5)] |
graph[3] |
[] |