Gevşetme
- Algoritmalar kursu
- İleri seviye
- Ders 31/56
- 4 dk
Kenar üzerinden daha kısa yol bulunca mesafeyi güncellemeyi öğrenirsin.
Gevşetme
Bir düğüm seçilince komşuları gevşetilir: dist[v] = min(dist[v], dist[u] + w). Eğer u'dan v'ye daha kısa yol bulunursa mesafe güncellenir.
Bu işlem, her kenar için en fazla bir kez yapılır. Gevşetme, Dijkstra'nın temel adımıdır.
Döngü yapısı
Dijkstra bir döngü içinde çalışır: her turda en küçük mesafeli ziyaret edilmemiş düğüm seçilir, komşuları gevşetilir. Tüm düğümler ziyaret edilince biter.
Bu yapı, algoritmanın her turda bir düğümü kesin olarak işaretlemesini sağlar. Karmaşıklık O(n²)'dir.
Uygulama dijkstra fonksiyonu
dijkstra(graph, src) yaz. Her turda en küçük ziyaret edilmemiş düğümü seç, komşuları gevşet. print(dijkstra(init_graph(), 0)) ile [0, 3, 1, 4] yazdır.
Başlangıç kodu
def init_graph():
# Komşuluk listesini döndür
return [[(1, 4), (2, 1)], [(3, 1)], [(1, 2), (3, 5)], []]
def dijkstra(graph, src):
# Tek kaynak en kısa yolları bulÖrnek çözüm
def init_graph():
# Komşuluk listesini döndür
return [[(1, 4), (2, 1)], [(3, 1)], [(1, 2), (3, 5)], []]
def dijkstra(graph, src):
# Tek kaynak en kısa yolları 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
print(dijkstra(init_graph(), 0))Beklenen çıktı
[0, 3, 1, 4]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Gevşetme: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
dist[u] |
Kaynak mesafe |
w |
Kenar ağırlığı |
dist[v] |
Hedef mesafe |
min |
Küçük olan |
2 0'dan 3'e en kısa mesafe nedir?
- 5
- 6
- 4 Doğru cevap
- 1
Açıklama: 0→2→1→3 yolu 1+2+1=4 verir.
3 gevşetme koşulu
if dist[u] + w ____ dist[v]:if dist[u] + w < dist[v]:Açıklama: < doğru.