Özet - Dijkstra
- Algoritmalar kursu
- İleri seviye
- Ders 32/56
- 4 dk
Küçük graph'ta Dijkstra uygulayıp mesafeleri yazdıran mini görev yaparsın.
Özet - Dijkstra
Bu grupta tek kaynaktan tüm düğümlere en kısa yolu bulan Dijkstra algoritmasını öğrendin. Komşuluk listesi, mesafe dizisi ve gevşetme birleşince çözüm oluşur.
Şimdi tüm parçaları bir araya getiren bir sorgu fonksiyonu yazacaksın. Bu özet, grubun kavramlarını tek bir kodda birleştirir.
Uygulama shortest_path fonksiyonu
shortest_path(graph, src, dst) yaz. Dijkstra çalıştır, dist[dst]'yi döndür. print(shortest_path(init_graph(), 0, 3)) ile 4 yazdır.
Başlangıç kodu
def shortest_path(graph, src, dst):
# Dijkstra ile src→dst mesafesini bulÖrnek çözüm
def shortest_path(graph, src, dst):
# Dijkstra ile src→dst mesafesini bul
n = len(graph)
dist = [float('inf')] * n
dist[src] = 0
visited = [False] * n
for _ in range(n):
u = -1
best = float('inf')
for i in range(n):
if not visited[i] and dist[i] < best:
best = dist[i]
u = i
if u == -1:
break
visited[u] = True
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return dist[dst]
print(shortest_path(init_graph(), 0, 3))Beklenen çıktı
4
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Dijkstra'nın çıktısı nedir?
- Ziyaret dizisi
- Tek bir yol
- Kenar listesi
- Mesafe dizisi Doğru cevap
Açıklama: Çıktı kaynaktan tüm düğümlere mesafe dizisidir.
2 n ataması
Soru
n = len(____)
Cevap
n = len(graph)Açıklama: graph doğru.
3 Özet - Dijkstra: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
init_graph |
Graf |
init_dist |
Mesafe |
dijkstra |
Algoritma |
dist |
Çıktı |