Tüm Çiftler için Floyd-Warshall
Her çift arasındaki en kısa yolları bulun.
Tüm Çiftler için Floyd-Warshall, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 4. 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 Bir Arada
Bazen yalnızca bir kaynaktan değil, her düğüm çifti arasındaki en kısa yolu bulmanız gerekir. Bu, tüm çiftler problemidir.
Floyd-Warshall ile Tanışın
Floyd-Warshall, üç düzenli iç içe döngüyle ve neredeyse hiç hazırlık yapmadan tüm çiftler için eksiksiz bir uzaklık tablosu oluşturur.
Uzaklık Matrisi
dist[i][j] değerinin i'den j'ye bilinen en iyi maliyeti gösterdiği bir matris kullanın. Matrisi size verilen doğrudan kenarlardan oluşturun.
dist = [[INF] * n for _ in range(n)]Köşegeni Ayarlayın
Her düğüm kendisine ücretsiz ulaşabildiğinden, gevşetmeye başlamadan önce köşegen üzerindeki dist[i][i] değerini sıfıra ayarlayın.
for i in range(n):
dist[i][i] = 0Ara Düğüm Fikri
Teknik şudur: yolların bir ara düğüm k üzerinden geçmesine izin verin, ardından k üzerinden gitmenin doğrudan gitmekten ucuz olup olmadığını kontrol edin.
Döngü Sırası Önemlidir
Dış döngü k'dır; seçilen orta noktayı bu temsil eder. İçteki i ve j döngüleri, her çifti bu orta noktaya göre dener.
for k in range(n):
for i in range(n):
for j in range(n):Gevşetme Adımı
Her çift için k üzerinden gevşetin: i'den k'ye, ardından j'ye gitmek daha kısaysa dist[i][j] değerini bu birleşik maliyetle güncelleyin.
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]k Neden Dışarıda
k tamamlandığında tüm çiftler k'ye kadar olan ara düğümleri kullanabilir. k'yı en dışa koymak bu garantinin doğru kalmasını sağlar.
Negatif Kenarlar Sorun Değildir
Floyd-Warshall negatif kenarları kabul eder, ancak negatif döngüleri kabul etmez. Negatif bir döngü, bazı köşegen girdilerini sıfırın altına indirir.
Çalışma Süresi
n düğüm üzerinde üç döngü O(n^3) zaman ve O(n^2) bellek alanı gerektirir; bu yöntem yalnızca n birkaç yüzü geçmediğinde uygulanabilirdir.
Ne Zaman Seçilmeli
Graf küçük ve yoğunsa ve tek bir kaynaktan değil gerçekten her düğüm çifti arasındaki uzaklığa ihtiyacınız varsa Floyd-Warshall'ı seçin.
Hızlı Kontrol
Floyd-Warshall'da hangi döngü en dışta olmalıdır?
Özet: Floyd-Warshall
Bir matris başlatın, köşegeni sıfırlayın, ardından k, i, j sırasıyla döngü kurup k üzerinden gevşetin. O(n^3) sürede tüm çiftler arasındaki en kısa yolları bulun. 🧮
Sıkça Sorulan Sorular
“Tüm Çiftler için Floyd-Warshall” dersi ücretsiz mi?
Evet — “Tüm Çiftler için Floyd-Warshall” 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.
“Tüm Çiftler için Floyd-Warshall” dersinde ne öğreneceğim?
Her çift arasındaki en kısa yolları bulun. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
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 4. dersidir.
“Tüm Çiftler için Floyd-Warshall” 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.
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.
Bu kursun tüm dersleri
- Yığınla Dijkstra
- Deque ile 0-1 BFS
- Bellman-Ford ve Negatif Kenarlar
- Tüm Çiftler için Floyd-Warshall