Floyd Warshall Algorithm

+10

n düğümlü, 0 ile n-1 arasında numaralandırılmış yönlü bir çizge, n çarpı n boyutunda bir matris olarak verilmiştir: matrix[i][j], i düğümünden j düğümüne giden kenarın ağırlığıdır veya böyle bir kenar yoksa -1 değerini alır; matrix[i][i] ise 0 değerini alır. Bir yolun uzunluğu, kenar ağırlıklarının toplamıdır.

Her bir [i][j] girdisi, i düğümünden j düğümüne giden en kısa yolun uzunluğunu ya da i düğümünden j düğümüne ulaşılamıyorsa -1 değerini içeren n çarpı n boyutunda bir matris döndür.

Fonksiyon

shortestDistances(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: kenar ağırlıkları: matrix[i][j], i düğümünden j düğümüne olan kenarın ağırlığıdır veya kenar yoksa -1'dir
Döndürürinteger-2d-array: her düğüm çifti arasındaki en kısa mesafe; yol yoksa -1

Kısıtlar

1 ≤ n ≤ 100, burada n = matrix.length = matrix[i].length
matrix[i][i] = 0
i ≠ j olduğunda, matrix[i][j] değeri -1 (kenar yok) ya da 0 ≤ matrix[i][j] ≤ 1000 olur.
Kenarlar tek yönlüdür: matrix[i][j] ve matrix[j][i] birbirinden bağımsızdır.

Örnekler

Girdi: matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
Çıktı: [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
Açıklama: 1 numaralı düğüm üzerinden, 0 numaralı düğüm 2 numaralı düğüme 11 yerine 6 maliyetle ve 3 numaralı düğüme 9 maliyetle ulaşır. 1 numaralı düğüm, 2 numaralı düğüm üzerinden 0 numaralı düğüme 3 maliyetle ulaşır. 3 numaralı düğümden hiçbir yere çıkış olmadığından, satırının köşegen dışındaki değeri -1'dir.

Girdi: matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
Çıktı: [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
Açıklama: 2'den 1'e giden kenarın ağırlığı 0 olduğundan, 0 → 2 → 1 maliyeti 1'dir ve bu, doğrudan maliyet olan 6'dan düşüktür. 1. düğümden çıkan veya 0. düğüme giren kenar olmadığından, bu çiftler -1 olarak kalır.

Ek soru

Tabloyu oluşturduktan sonra bir kenarın maliyeti düşer. O(n³) döngülerini yeniden çalıştırmak yerine O(n²) içinde tüm uzaklıkları güncelleyebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her düğüm çifti için en kısa yola ihtiyacın var. Floyd-Warshall, tek bir üçlü döngüyle n² yanıtın tamamını bulur. Her tur, rotaların bir düğüm daha fazla yerde durmasına olanak tanır ve düğüm çifti başına bir karşılaştırmaya mal olur: şimdiye kadarki en iyi rota ile yeni düğüm üzerinden geçen rota.

Hiçbir şey değişmeyene kadar her rotayı bir kenar uzatın

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Matrisi başlangıç noktası alın ve her geçişte her yolu bir kenar uzatın: i noktasından m noktasına giden bir yol ile m → j kenarı, daha kısaysa i noktasından j noktasına giden bir yol olarak tutulur. Hiçbir şey değişmeyene kadar tekrarlayın.

p geçişten sonra, en fazla p+1 kenardan oluşan her en kısa yol bulunmuş olur. Hiçbir ağırlık negatif olmadığından, en kısa yollardan biri döngü içermez ve en fazla n-1 kenardan oluşur; böylece tüm uzaklıklar kesinleştiğinde geçişler durur. 100 düğüm için bir geçiş n³ = 10^6 adım sürer ve uzun bir en kısa yol zinciri n geçişe kadar gerektirebilir: O(n⁴), en fazla 10^8 adım.

Algoritma

matrix'i dist'e kopyalayın.
Her i, m ve j için: hem dist[i][m] hem de matrix[m][j] varsa toplamlarını hesaplayın.
dist[i][j] -1 ise veya toplamdan büyükse toplamı kaydedin ve geçişin bir şeyi değiştirdiğini not edin.
Hiçbir şeyi değiştirmeyene kadar geçişi tekrarlayın, ardından dist'i döndürün.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the routes of one edge; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    changed = True
    while changed:
        changed = False
        # One pass: a route from i that ends at m may grow by the edge m -> j.
        for i in range(n):
            for m in range(n):
                if dist[i][m] == -1:
                    continue
                for j in range(n):
                    edge = matrix[m][j]
                    if edge == -1:
                        continue
                    via = dist[i][m] + edge
                    if dist[i][j] == -1 or via < dist[i][j]:
                        dist[i][j] = via
                        changed = True
    return dist

Floyd-Warshall: her turda bir durak daha kullanılmasına izin ver

Sezgi

Bir rotanın uç noktaları arasında hangi düğümlerde durabileceğini sınırla. Tablo başlangıçta matristir; yani durak içermeyen rotaları gösterir. k turundan sonra dist[i][j], duraklarının tümü 0 ile k arasındaki düğümlerde bulunan en kısa rotadır ve son tur yanıtı verir.

k turunda, k düğümünde de durabilen en iyi rota ya k düğümünü atlar ve tabloda zaten bulunur ya da negatif ağırlık olmadığı için k düğümünden bir kez geçer. Bu rotanın iki yarısı yalnızca 0 ile k-1 arasındaki düğümlerde durur; dolayısıyla bunlar dist[i][k] ve dist[k][j] olur.

İlk örnekte, 1. tur doğrudan 0 düğümünden 2 düğümüne giden 11 uzunluğundaki rotayı 6 ile değiştirir. 2. turda, 0 düğümünden 3 düğümüne giden rota 6 + 3 = 9 olur; burada 1 düğümündeki durak, 6'nın içindedir.

Tek bir tablo yeterlidir: k turunda k satırı ve k sütunu değişmez, çünkü dist[k][k] 0'dır.

Algoritma

matrix'i dist'e kopyala; -1 henüz rota bulunmadığı anlamına gelir.
k için 0'dan n-1'e kadar ve her i ile j için: dist[i][k] veya dist[k][j] -1 ise çifti atla.
Aksi takdirde via = dist[i][k] + dist[k][j] değerini hesapla.
dist[i][j] -1 ise veya via'dan büyükse, değerini via olarak ayarla.
dist'i döndür.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the direct edges; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    # After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == -1:
                continue
            for j in range(n):
                if dist[k][j] == -1:
                    continue
                via = dist[i][k] + dist[k][j]
                if dist[i][j] == -1 or via < dist[i][j]:
                    dist[i][j] = via
    return dist

Tuzaklar ve uç durumlar

-1'i bir ağırlık gibi eklemek: -1 + 5 = 4 bir rota gibi görünür. Önce her iki parçayı da kontrol edin ve dist[i][j] içindeki -1'i herhangi bir rotadan daha kötü kabul edin.
k üzerindeki döngüyü içeriye almak. 0 ile k-1 arasındaki duraklardan geçen rotalar, k düğümü değerlendirmeye alınmadan önce kesinleşmiş olmalıdır.
En büyük int değerini sonsuzluk olarak kullanmak: iki değer toplandığında 32 bitlik bir int taşarak negatif bir mesafeye dönüşür. Gerçek bir mesafe en fazla 99 × 1000 = 99,000 olduğundan, 10^9 güvenlidir; çünkü 2 × 10^9, 2^31-1 değerinden küçüktür.
Kenarların iki yönde de olduğunu varsaymak. İkinci örnekte 0 düğümünden 1 düğümüne ulaşılabilir, ancak 1 düğümünden hiçbir yere ulaşılamaz.
Ağırlıkları yok sayan genişlik öncelikli arama çalıştırmak: ilk örnekte, 0 düğümünden 2 düğümüne olan mesafeyi 6 değil, 11 olarak bildirir.

Sıkça sorulan sorular3

Floyd Warshall algoritmasının zaman karmaşıklığı nedir?

n düğüm için O(n³) zaman: düğümler üzerinde iç içe üç döngü; her adımda bir toplama ve bir karşılaştırma, 100 düğüm için 10^6 adım. Uzaklık tablosu için alan O(n²)’dir ve tablo yerinde güncellenebilir.

Floyd Warshall negatif kenar ağırlıklarıyla çalışır mı?

Evet, negatif bir döngü, yani ağırlıklarının toplamı 0'dan küçük olan bir döngü olmadığı sürece. Negatif bir döngü varsa en kısa yollar tanımlı değildir ve tablo bunu gösterir: bazı dist[i][i] değerleri 0'ın altında kalır.

Floyd Warshall algoritmasını Dijkstra algoritması yerine ne zaman kullanmalısınız?

Birkaç yüz düğüme kadar olan yoğun bir grafikte her düğüm çifti için Floyd-Warshall kullanın. Her düğümden Dijkstra çalıştırmak, bir diziyle O(n³), bir yığınla O(n · E log n) maliyetlidir; büyük ve seyrek graflarda bu daha avantajlıdır. Floyd-Warshall yığın gerektirmez ve Dijkstra'nın kabul etmediği negatif kenarları kabul eder.

def shortestDistances(matrix):
    # Kodu buraya yazın

Test #1

Test #2

Argüman

matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]

Beklenen Çıktı

[[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]