Tek kaynak

Bir kaynaktan tüm düğümlere en kısa yolu bulan algoritmayı öğrenirsin.

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.

init_graph() yaz. Komşuluk listesini döndür. print(init_graph()) ile 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)], []]
print(init_graph())

kenar ağırlığı

graph[0] = [(1, ____)]

Cevabı göster

graph[0] = [(1, 4)]