Floyd–Warshall algoritması
Eski yol atlaslarının arkasında bir tablo olurdu: her şehir çifti arasındaki uzaklık. Floyd–Warshall böyle bir tabloyu hesaplamanın bir yoludur ve şimdiye kadar yazılmış en kısa algoritmalardan biridir: üç döngü, bir karşılaştırma ve tüm en kısa uzaklıklar yerine oturur.
Temel fikir
Dijkstra algoritması ve Bellman–Ford en kısa uzaklıkları tek bir başlangıçtan bulur. Floyd–Warshall ise her düğümden diğer her düğüme olan uzaklıkları tek seferde, her düğüm için bir satırı ve bir sütunu olan bir tabloda bulur. Kenarların doğrudan söylediğiyle başlar, sonra yolda ara durak olarak giderek daha fazla düğüme izin vererek tüm tabloyu iyileştirir.
Adım adım
Tabloyu doldurun: her düğümden kendisine 0, komşular arasında kenarın uzunluğu, başka her yerde sonsuz. Sonra her k düğümü ve her i, j çifti için: i'den k'ye uzaklık ile k'den j'ye uzaklığın toplamı i'den j'ye uzaklıktan küçükse küçük sayıyı yazın. Algoritmanın tamamı bu. Kodda k en dışta olmak üzere üç döngüdür.
Bir örnek
Uzunluğu 3 olan A–B, 1 olan B–C, 5 olan A–C ve 2 olan C–D kenarlarına sahip dört düğüm alın. Tablo bunlarla, A–D ve B–D için de sonsuzla başlar. A turu hiçbir şeyi değiştirmez, çünkü A üzerinden giden her yol daha uzundur. B turu, A'dan C'ye B üzerinden yolu bulur: 3 + 1 = 4, 5'ten kısa. C turu, A'dan D'ye C üzerinden 4 + 2 = 6 ve B'den D'ye 1 + 2 = 3 yollarını bulur; ikisi de bulunan ilk yollardır. D turu hiçbir şeyi değiştirmez. Son tablo: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.
Döngülerin sırası neden önemli
Ara durak k en dış döngü olmalıdır. k'nin turundan sonra her hücre, yalnızca ilk k düğümü ara durak olarak kullanan en kısa uzaklıktır ve sonraki tur bunun üzerine kurulur: yeni ara duraktan geçen en iyi yol, ona giden en iyi yol ile ondan çıkan en iyi yolun toplamıdır ve ikisi de zaten doğrudur. k'yi iç döngüye koymak bu güvenceyi bozar ve yanlış uzaklıklar bırakabilir. Bir tur sırasında tabloyu yerinde güncellemek güvenlidir, çünkü k'nin kendi satırı ve sütunu o turda değişmez.
Tarihçe ve kullanım alanları
Bernard Roy yöntemi 1959'da tanımladı. 1962'de Stephen Warshall onu yalnızca bir düğümün diğerine ulaşıp ulaşamadığını soran geçişli kapanış için, Robert Floyd ise en kısa yollar için yayımladı. Yöntem uzaklık tablolarını ve yönlendirme tablolarını hesaplar, bir ağın çapını bulur, hangi düğümün hangisine ulaşabildiğini söyler ve köşegendeki negatif bir hücreyle negatif bir döngüyü ele verir.
Keşfedin
Uygulamayı açın ve Adım'a basın. Graf bir tarafta, tablo diğer taraftadır. Her tur, şu anki ara durağın satırını ve sütununu vurgular; her adım bir çiftin daha kısa uzaklığını yazar ve toplanan iki hücrenin çevresini çizer. Bu turda değişen hücreler renklidir. Tablo tamamlandığında aralarındaki en kısa yolu görmek için bir başlangıç ve bir hedef seçin.
Sık sorulan sorular
Floyd–Warshall'ın zaman karmaşıklığı nedir?
Kenar sayısı ne olursa olsun n düğüm için O(n³), tablo için de O(n²) bellek. Basit döngüsünün çok hızlı çalıştığı küçük ya da yoğun graflar için ilk tercih edilen yöntemdir.
Floyd–Warshall mı, her düğümden Dijkstra mı?
Yoğun bir grafta ya da kenarlar negatif olabildiğinde Floyd–Warshall daha basittir ve aşağı yukarı aynı hızdadır. Negatif kenarı olmayan büyük seyrek bir grafta Dijkstra algoritmasını her düğümden çalıştırmak daha hızlıdır.
Floyd–Warshall dinamik programlama mıdır?
Evet. Ara durakları ilk k düğüm arasında olan yollar için problemi, ilk k − 1 düğümün yanıtlarını kullanarak çözer ve yalnızca bir tablo tutar; ilerledikçe onun üzerine yazar.
Geçişli kapanış nedir?
Uzaklıklar dikkate alınmadan hangi düğümün hangisine ulaşabildiğini gösteren tablo. Algoritmanın Warshall sürümü bunu "min" ve "+" yerine "veya" ve "ve" ile hesaplar.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Floyd–Warshall'ı deneyin