Coding Interview Prep · Ders

Floyd-Warshall: Tüm Çiftler İçin En Kısa Yollar

Q: “Floyd-Warshall: Tüm Çiftler İçin En Kısa Yollar” dersi ücretsiz mi?

Evet — “Floyd-Warshall: Tüm Çiftler İçin En Kısa Yollar” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.

Q: Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.

Q: “Floyd-Warshall: Tüm Çiftler İçin En Kısa Yollar” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Q: Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Üç iç içe döngülü Floyd-Warshall algoritmasını kullanarak tüm çiftlerin uzaklık matrisini doldurun ve tüm düğüm çiftleri arasındaki en az sıçrama sayısını bulun.

Floyd-Warshall: Tüm Çiftler İçin En Kısa Yollar, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.

Tüm Çiftler Arası En Kısa Yollar

Floyd-Warshall, negatif kenar ağırlıkları içeren graflar da dâhil olmak üzere (ancak negatif çevrimler içermeyen) ağırlıklı bir graftaki her düğüm çifti arasındaki en kısa yolları hesaplar. Her kaynaktan Dijkstra çalıştırmak O(V × (V+E) log V) sürerken Floyd-Warshall, kenar yoğunluğundan bağımsız olarak O(V³) zamanda çalışır. V ≤ 500 olan yoğun graflarda Floyd-Warshall çoğu zaman daha basit ve benzer hızdadır.

Temel Fikir: Ara Düğümler

Floyd-Warshall'ın temel fikri şudur: dp[i][j][k] = ara düğüm olarak yalnızca {0, 1, ..., k} düğümlerini kullanarak i'den j'ye giden en kısa yol. En kısa yol ya k düğümünü ara düğüm olarak kullanır ya da kullanmaz. Kullanıyorsa: dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. Kullanmıyorsa: dp[i][j][k] = dp[i][j][k-1]. Üçüncü boyut yalnızca ileri doğru ilerlediği için ortadan kaldırılabilir; güncellemeyi yerinde yaparız.

Uzaklık Matrisinin Başlatılması

V×V boyutunda bir matrisle başlayın: dist[i][i] = 0 (sıfır öz uzaklık), doğrudan kenarlar için dist[i][j] = weight ve kenar bulunmayan çiftler için dist[i][j] = inf. Ardından tüm ara düğüm k değerleri üzerinde dolaşarak (i, j) çiftlerini güncelleyin. İzin verilen ara düğüm kümesini doğru şekilde genişleterek yolları oluşturabilmemiz için k üzerindeki dış döngü önce gelmelidir.

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w  # directed graph
    
    for k in range(V):       # intermediate node
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

Örnekle Eksiksiz Uygulama

Floyd-Warshall'ı 4 düğümlü bir graf üzerinde adım adım izleyelim. Her bir ara düğüm k işlendikten sonra matris, k düğümünden geçen daha kısa yollarla dolar. Algoritma, en kısa yolları aşamalı olarak oluşturarak birden fazla atlamayı doğal biçimde ele alır.

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

V = 4
edges = [(0,1,3),(0,2,7),(1,2,1),(1,3,5),(2,3,2)]
dist = floyd_warshall(V, edges)
for row in dist:
    print([x if x != float('inf') else 'INF' for x in row])

Negatif Çevrimleri Algılama

Floyd-Warshall çalıştırıldıktan sonra ana köşegeni kontrol edin: herhangi bir dist[i][i] < 0 ise i düğümünden geçen bir negatif çevrim vardır. Bunun nedeni, negatif bir çevrimin i düğümünden yine i düğümüne negatif maliyetle ulaşmayı mümkün kılmasıdır. Negatif çevrim yoksa tüm köşegen girdileri 0 olarak kalır.

def has_negative_cycle_fw(V, edges):
    dist = floyd_warshall(V, edges)
    for i in range(V):
        if dist[i][i] < 0:
            return True  # negative cycle through node i
    return False

# Negative cycle: 0->1->2->0 with weights 1,-3,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-3),(2,0,1)]
print(has_negative_cycle_fw(3, edges_neg))  # True

Yolun Yeniden Oluşturulması

i'den j'ye giden gerçek yolu yeniden oluşturmak için bir next[i][j] matrisi tutun: doğrudan kenarlar için başlangıçta next[i][j] = j olsun. k ara düğümü üzerinden güncelleme yaparken next[i][j] = next[i][k] atayın. Yolu elde etmek için i ile başlayın ve j'ye ulaşana kadar next işaretçilerini izleyin. Bu yöntem O(V²) ek alan ve yol başına O(V) yeniden oluşturma maliyeti ekler.

def fw_with_path(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    nxt = [[None]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w; nxt[u][v] = v
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt

def get_path(nxt, i, j):
    if nxt[i][j] is None: return []
    path = [i]
    while i != j:
        i = nxt[i][j]; path.append(i)
    return path

Geçişli Kapanış

Daha basit bir türev olan Geçişli Kapanış, tüm çiftler için "j düğümüne i düğümünden ulaşılabilir mi?" sorusunu yanıtlar. Uzaklıkları mantıksal değerlere dönüştürün: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). Bu, toplama ve minimum yerine mantıksal OR kullanan Floyd-Warshall'dır. reach[i][i] = True değerini ve doğrudan kenarlar için reach[i][j] = True değerini başlatın.

def transitive_closure(V, edges):
    reach = [[False]*V for _ in range(V)]
    for i in range(V):
        reach[i][i] = True
    for u, v, _ in edges:
        reach[u][v] = True
    for k in range(V):
        for i in range(V):
            for j in range(V):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
    return reach

edges = [(0,1,1),(1,2,1)]
R = transitive_closure(3, edges)
print(R[0][2])  # True (0 can reach 2 via 0->1->2)

Karmaşıklık ve Kullanım Zamanı

Floyd-Warshall: O(V³) zaman, O(V²) alan. V ≤ 300 olan yoğun graflarda (E ≈ V²), Dijkstra'yı V kez çalıştırmaktan daha hızlıdır; bu durumda onun da karmaşıklığı O(V³) olur. V = 1000 ve E = 3000 olan seyrek graflarda V Dijkstra çalıştırmanın maliyeti O(V×E×log V) ≈ 33M iken Floyd-Warshall'ın maliyeti O(V³) = 10⁹ olur; Dijkstra kazanır. Her birinin ne zaman uygun olduğunu bilin.

Tüm Düğüm Çiftleri Arasındaki En Az Atlama Sayısı

Tüm kenar ağırlıklarını 1 yapın (veya toplama kullanarak min yerine Floyd-Warshall uygulayan bir boolean komşuluk matrisi kullanın): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Bu, tüm düğüm çiftleri arasındaki minimum atlama sayısını hesaplar — tek bir O(V³) Floyd-Warshall geçişiyle hesaplanan tüm çiftler için bir BFS sonucudur.

def min_hops_all_pairs(V, adj_list):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
        for j in adj_list[i]:
            dist[i][j] = 1
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

adj = [[1,2],[2],[3],[],[]]
print(min_hops_all_pairs(5, adj)[0])  # [0, 1, 1, 2, INF]

Mülakat Bağlamı: Mülakatçılar Floyd-Warshall Hakkında Sorduğunda

Floyd-Warshall; (1) küçük bir graf üzerinde tüm çiftler arasındaki mesafeleri bulma, (2) toplam ağırlığı negatif olan herhangi bir döngünün varlığını belirleme, (3) kısıt yayılımı problemlerinde en kısa yolları hesaplama ve (4) açıkça O(V³) çözümü isteyen, V ≤ 200 olan problemlerle ilgili mülakat sorularında karşınıza çıkar. Doğruluk için üç döngülü yapıyı ve negatif döngü bulunmaması gerektiğini mutlaka belirtin.

Floyd-Warshall ile Yönsüz Graflar

Yönsüz graflar için her kenarın iki yönünü de ekleyin: dist[u][v] = dist[v][u] = weight. Algoritmanın geri kalanı aynıdır. Ortaya çıkan matris simetriktir: tüm çiftler için dist[i][j] == dist[j][i]. Başlatma sırasında yönlü kenarları yanlışlıkla atamamaya dikkat edin — üç döngüyü çalıştırmadan önce yönsüz kenarlar başlangıç matrisine her iki yönde de eklenmelidir.

def fw_undirected(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
        dist[v][u] = w  # both directions for undirected
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Kısa Kontrol

Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını ne kadar anladığınızı sınayın.

Ders Özeti

Bu derste şunları öğrendiniz: Floyd-Warshall, üç iç içe döngü ve dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) yineleme bağıntısını kullanarak tüm düğüm çiftleri arasındaki en kısa yolları hesaplar, tamamlandıktan sonra herhangi bir dist[i][i] < 0 olup olmadığı kontrol edilerek negatif döngüler algılanabilir ve algoritma O(V³) zamanda ve O(V²) alanda çalışır. Sırada Ağ Gecikme Süresi ve yolun yeniden oluşturulması teknikleriyle en kısa yol uygulamalarını yeniden ele alıyoruz.

Sıkça Sorulan Sorular