Gevşetme

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.

Örnek çözümü göster

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))

Kendini test et

Gevşetme: kavramları eşleştir

dist[u]

Kaynak mesafe
w

Kenar ağırlığı
dist[v]

Hedef mesafe
min

Küçük olan
0'dan 3'e en kısa mesafe nedir?
- 5
- 6
- 4
- 1
Cevabı göster

4 — 0→2→1→3 yolu 1+2+1=4 verir.

gevşetme koşulu

if dist[u] + w ____ dist[v]:

Cevabı göster

if dist[u] + w < dist[v]:

Sıradaki ders: Özet - Dijkstra

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler