Network Delay Time

Q: Network Delay Time'ın zaman karmaşıklığı nedir?

Dijkstra algoritması ve ikili yığın kullanıldığında karmaşıklık O(E log E) olur; burada E, bağlantıların sayısıdır. Bu, O(E log n) ile aynıdır; çünkü E en fazla n² olabilir. Komşuluk listesi, süreler ve yığın O(n + E) alan kullanır. Bellman-Ford algoritması O(n · E) zaman ve O(n) alan gerektirir.

Q: Dijkstra algoritması neden negatif olmayan ağırlıklara ihtiyaç duyar?

Dijkstra, geçici zamanı en küçük olan düğümü kesinleştirir ve ona bir daha bakmaz. Bu, ancak daha sonra bulunan hiçbir güzergâh daha kısa olamayacaksa güvenlidir; negatif olmayan ağırlıklarda, kesinleştirilmemiş bir düğümden geçen her güzergâhın maliyeti en az o düğümün zamanı kadardır. Negatif bir bağlantı bu mantığı bozar: daha maliyetli görünen bir düğümden geçen güzergâh yine de daha ucuz olabilir. Negatif ağırlıklar için Bellman-Ford kullanın.

Q: Ağ Gecikme Süresi için neden BFS kullanmamalı?

BFS, düğümleri başlangıçtan kaç bağlantı uzakta olduklarına göre ziyaret eder; bu, yalnızca her bağlantı aynı süreyi aldığında varış zamanıyla örtüşür. Burada bağlantı süreleri farklı, dolayısıyla daha fazla bağlantı içeren bir rota daha önce varabilir. Tüm süreler eşit olsaydı BFS yeterli olurdu; süreler yalnızca 0 ve 1 olduğunda ise deque tabanlı 0-1 BFS işe yarar.

Q: Network Delay Time problemini yığın kullanmadan çözebilir misin?

Evet. Sade bir dizi kullanan Dijkstra, en küçük süreyi bulmak için kesinleşmemiş tüm düğümleri tarar; bu işlem toplamda O(n²) maliyetlidir ve yığın gerektirmez. E'nin n²'ye yakın olduğu yoğun graflarda bu daha iyi bir seçimdir. Buradaki 3.000 düğüm ve 4.000 bağlantı içeren büyük testler gibi seyrek graflarda ise yığın sürümü çok daha az iş yapar.

OrtaEn kısa yollar Graflar Yığın (heap)

+10

Bir ağda n düğüm vardır ve bunlar 1'den n'ye kadar etiketlenmiştir. Bağlantılar, times adlı bir liste olarak verilir; burada times[i] = [u, v, w], düğüm u'dan gönderilen bir sinyalin w zaman birimi sonra düğüm v'ye ulaştığı anlamına gelir. Bağlantılar yalnızca tek yönde çalışır.

Bir sinyal, k düğümünden 0 anında yola çıkar ve ulaşabildiği tüm bağlantılar boyunca ilerler. Son düğümün sinyali aldığı zamanı döndür; herhangi bir düğüm sinyali hiç almazsa -1 döndür.

Fonksiyon

networkDelayTime(times: integer-2d-array, n: integer, k: integer) → integer

timesinteger-2d-array: yönlü bağlantılar, her biri [u, v, w] biçiminde
ninteger: düğüm sayısı
kinteger: sinyali gönderen düğüm
Döndürürinteger: sinyalin son düğüme ulaştığı zaman veya -1

Kısıtlar

2 ≤ n ≤ 3000
1 ≤ times.length ≤ 4000
times[i].length = 3
1 ≤ u, v ≤ n ve u ≠ v
0 ≤ w ≤ 100
Hiçbir iki bağlantı aynı u ve aynı v değerlerini birlikte paylaşmaz.
1 ≤ k ≤ n

Örnekler

Girdi: times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
Çıktı: 4
Açıklama: 3. düğüm sinyali 1. zamanda duyar. 2. düğüm doğrudan bağlantısı üzerinden sinyali 4. zamanda duyabilir, ancak 3. düğüm üzerinden geçen yol sinyali 1 + 2 = 3. zamanda ulaştırır ve 4. düğüm sinyali 3 + 1 = 4. zamanda duyar. En son 4. düğüm duyar; bu, 4. zamandadır.

Gönderirken +16 gizli test

Ek soru

Sinyalin m bağlantıyı geçtikten sonra zayıfladığını varsayalım. Bu sınır altında son düğümün sinyali ne zaman duyacağını nasıl bulursunuz?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Her düğüm sinyali, k noktasından kendisine ulaşan en hızlı yolun süresi kadar zamanda alır; dolayısıyla görev, yönlü bir grafikte tek kaynaklı en kısa yolları bulup ardından maksimumu almaktır. Yanıt, en büyük en kısa süredir; herhangi bir düğüme ulaşan bir yol yoksa -1'dir. Bağlantı süreleri hiçbir zaman negatif değildir; bu sayede Dijkstra algoritması, bir min-yığın kullanarak her düğümü varış sırasına göre bir kez kesinleştirir. Aşağıda E, bağlantı sayısı olan times.length değeridir.

Her daha hızlı rotada yeniden ziyaret eden derinlik öncelikli arama

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

Sezgi

Aramaya k düğümünde zaman 0 ile başla ve şu ana kadarki zamanı yanında taşıyarak her bağlantıyı izle. Her düğüm için şimdiye kadar görülen en hızlı varış zamanını kaydet. Arama bir düğüme, kaydedilmiş zamandan daha erken olmayan bir zamanda ulaştığında orada dur: o rotanın ileride sağlayabileceği her şeyi daha hızlı rota zaten sağlamıştır. Düğüme daha erken ulaştığında kayıt güncellenir ve düğümün ilerisindeki her şey de iyileşebilir; bu yüzden arama oradan devam eder.

Bu yöntem her zaman doğrudur. Arama yalnızca hiçbir rota herhangi bir kaydı iyileştirmediğinde durur ve her düğüme giden en hızlı rota bir noktada o düğümün kaydını iyileştirir; dolayısıyla her kayıt gerçek en hızlı zamanla sonuçlanır.

Sorun, bir düğümün kaç kez iyileştirilebileceğidir. Derinlik öncelikli arama, karşılaştığı ilk bağlantıyı sonuna kadar izler; bu nedenle bir düğüme önce yavaş bir rotayla, sonra biraz daha hızlı bir rotayla, ardından yeniden daha hızlı bir rotayla ulaşabilir ve her seferinde düğümün ilerisindeki her şeyi dolaşabilir. Arka arkaya dizilmiş 18 kapı düşün. Her iki kapı arasında ücretsiz bir bağlantı ya da süreleri toplamı 65,536, 32,768 ve bu şekilde 1'e kadar azalan bir bağlantı zinciri olan dolambaçlı bir rota seçebilirsin. Önce dolambaçlı rotaları deneyen arama, son kapıya birbirinden farklı 131,072 zamanda ulaşır ve her biri bir öncekinden daha erkendir; ayrıca her seferinde arkasındaki 1,700 düğümü dolaşır: yaklaşık 220 milyon adım. Büyük testlerden ikisi bu şekilde oluşturulmuştur: birinde her dolambaçlı rota ücretsiz bağlantısından önce, diğerindeyse sonra listelenir; böylece bağlantıları hangi sırayla denerse denesin arama bu testlerden birinde takılır.

Algoritma

Bir komşuluk listesi oluştur: her düğüm için, düğümden çıkan bağlantıları ve bunların sürelerini listele.
Her düğümün en iyi zamanını sonsuz olarak ayarla ve (k, 0) değerini bir yığına ekle.
(node, t) değerini yığından çıkar. t, best[node] değerinden küçük değilse bu adımı atla; aksi takdirde best[node] = t olarak ayarla.
node düğümünden çıkan ve varış zamanı best[next] değerinden daha iyi olan her bağlantı için (next, t + w) değerini yığına ekle.
Yığın boşaldığında, herhangi bir en iyi zaman hâlâ sonsuzsa -1 döndür; aksi takdirde en büyük olanı döndür.

def networkDelayTime(times, n, k):
    graph = [[] for _ in range(n + 1)]
    for u, v, w in times:
        graph[u].append((v, w))
    INF = float("inf")
    best = [INF] * (n + 1)  # the fastest arrival found so far at each node
    stack = [(k, 0)]
    while stack:
        node, t = stack.pop()
        # A route that is not faster than one already found adds nothing.
        if t >= best[node]:
            continue
        best[node] = t
        # Push in reverse so the first listed edge is explored first.
        for nxt, w in reversed(graph[node]):
            if t + w < best[nxt]:
                stack.append((nxt, t + w))
    worst = 0
    for node in range(1, n + 1):
        if best[node] == INF:
            return -1
        worst = max(worst, best[node])
    return worst

Bellman-Ford: her kenarı en fazla n-1 kez gevşet

Sezgi

Her düğüm için geçici bir dist zamanı tut: k için 0, geri kalanı için sonsuz. u → v bağlantısını w zamanıyla gevşetmek şu anlama gelir: dist[u] + w, dist[v] değerinden küçükse bağlantı v'ye daha hızlı bir yol sunar; bu yüzden dist[v] değerini bu değere düşür. Bellman-Ford, tüm liste üzerinde geçişler yapar ve her geçişte her bağlantıyı gevşetir.

Peki bunun doğru zamanları bulmasını ne sağlar? Bir düğüme giden en hızlı rotayı ele alalım; örneğin k → a → b → v. İlk geçişte dist[k] zaten 0 olduğundan k → a gevşetilir ve böylece dist[a] kesinleşir. İkinci geçiş dist[b] değerini, üçüncü geçiş ise dist[v] değerini kesinleştirir. En hızlı bir rotanın bir düğümü iki kez ziyaret etmesi gerekmez; çünkü bir döngü hiçbir zaman negatif zaman almaz. Bu nedenle rotada en fazla n-1 bağlantı bulunur ve n-1 geçiş tüm düğümlerin değerini kesinleştirir. Hiçbir şeyi değiştirmeyen bir geçiş, sonraki geçişlerin de hiçbir şeyi değiştiremeyeceğini kanıtlar; bu yüzden orada durursun.

Her geçiş O(E) maliyetlidir; dolayısıyla en kötü durum O(n · E) olur. Listenin sırası, bunun ne kadar kötüleşeceğini belirler: uzun bir rotanın bağlantıları en uzaktaki uçtan başlangıca doğru sıralanırsa her geçiş bir düğüm daha kesinleştirir. Büyük testlerden biri tam olarak böyledir: geriye doğru sıralanmış 3,000 düğümlü bir zincir; 4,000 bağlantı üzerinde 2,999 geçiş gerektirir ve yaklaşık 12 milyon gevşetme yapar. Bu boyutta yine de zamanında çalışır, ancak iş miktarı n ile E'nin çarpımı oranında artar. Bellman-Ford'un asıl gücü başka yerdedir: bazı bağlantı zamanları negatif olduğunda da doğru sonuç verir; Dijkstra ise bu durumda başarısız olur.

Algoritma

dist[k] = 0 olarak ayarlayın ve diğer tüm dist değerlerini sonsuz olarak ayarlayın.
En fazla n-1 kez tekrarlayın: her bağlantı [u, v, w] için, dist[u] + w < dist[v] ise dist[v] = dist[u] + w olarak ayarlayın.
Hiçbir şeyi değiştirmeyen bir geçişten sonra erken durun.
Herhangi bir dist hâlâ sonsuzsa -1, aksi takdirde en büyük değeri döndürün.

def networkDelayTime(times, n, k):
    INF = float("inf")
    dist = [INF] * (n + 1)
    dist[k] = 0
    # A fastest route visits each node at most once, so it has at most n-1 edges,
    # and n-1 passes over every edge are enough to find it.
    for _ in range(n - 1):
        changed = False
        for u, v, w in times:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:  # a pass that improves nothing means every time is final
            break
    worst = 0
    for node in range(1, n + 1):
        if dist[node] == INF:
            return -1
        worst = max(worst, dist[node])
    return worst

Min yığın kullanan Dijkstra algoritması

Sezgi

Bellman-Ford, henüz süreleri kesinleşmemiş düğümlerden çıkan bağlantıları gevşettiği ve onlara geri dönmesi gerektiği için fazladan geçişler yapar. Dijkstra algoritması ise her düğümün bağlantılarını, süresi kesinleştiği anda tam olarak bir kez gevşetir. Soru, bunun ne zaman olduğunu nasıl bileceğimizdir.

Yanıt, açgözlü bir kuraldır: Henüz kesinleşmemiş düğümler arasında tahmini süresi en küçük olanın süresi zaten kesindir. Bu düğüme giden başka herhangi bir rota, bir noktada kesinleşmiş düğümlerden ayrılmak zorundadır; bunu da süresi en az aynı kadar büyük olan kesinleşmemiş bir düğüm üzerinden yapar. Bundan sonraki bağlantılar ise negatif olmadıkları için yalnızca süre ekleyebilir. Bu nedenle o düğümü kesinleştirir, bağlantılarını gevşetir ve işlemi tekrarlarız. İlk örnekte 1. düğümün süresi 0'da kesinleşir ve 2. düğüme 4, 3. düğüme 1 süresini sunar. 3. düğüm en küçük süreye sahiptir, 1'de kesinleşir ve 2. düğümün süresini 3'e düşürür. 2. düğüm 3'te kesinleşir ve 4. düğüme 4 süresini sunar; bu düğüm en son kesinleşir. Yanıt 4'tür.

Bir min-heap, tahmini süresi en küçük olanı hızlıca bulur. Bir düğümün süresi iyileştiğinde (time, node) ekle ve eski girdiyi bulmaya çalışmak yerine heap'te bırak. Eski girdi daha sonra heap'ten çıktığında, süresi düğümün güncel süresinden büyük olur; bu yüzden girdiyi atlayabilirsin. Her bağlantı en fazla bir girdi eklediğinden heap hiçbir zaman E + 1 girdiden fazlasını tutmaz ve her ekleme ya da çıkarma O(log E) maliyetindedir. Böylece toplam süre O(E log E) olur; bitişiklik listesi, süreler ve heap için gereken alan ise O(n + E)'dir.

Açgözlü kuralı güvenli kılan, sürelerin negatif olmamasıdır. Süresi 2 olan A → B, süresi 3 olan A → C ve süresi -2 olan C → B bağlantılarını ele alalım. Dijkstra, B düğümünün süresini 2'de kesinleştirir; ancak C üzerinden geçen rota bu düğüme 1'de ulaşır. Bir sinyal asla gönderilmeden önce ulaşamaz; dolayısıyla buradaki her süre en az 0'dır ve kural geçerlidir.

Algoritma

Her düğüm için (next, w) çiftlerinden oluşan bir komşuluk listesi oluştur.
dist[k] = 0 olarak ayarla, diğer tüm dist değerlerini sonsuz yap ve bir min-yığına (0, k) ekle.
En küçük (t, node) çiftini çıkar. t > dist[node] ise bu kayıt güncel değildir: atla.
Aksi hâlde t kesinleşmiştir. node düğümünden next düğümüne, süresi w olan her bağlantı için t + w < dist[next] ise dist[next] = t + w olarak ayarla ve (t + w, next) çiftini ekle.
Yığın boşaldığında, herhangi bir dist sonsuzsa -1 döndür; aksi hâlde en büyük olanı döndür.

import heapq


def networkDelayTime(times, n, k):
    graph = [[] for _ in range(n + 1)]
    for u, v, w in times:
        graph[u].append((v, w))
    INF = float("inf")
    dist = [INF] * (n + 1)
    dist[k] = 0
    heap = [(0, k)]  # (arrival time, node), smallest time on top
    while heap:
        t, node = heapq.heappop(heap)
        # A stale entry: this node was already reached sooner.
        if t > dist[node]:
            continue
        # t is now final: every other route reaches node later.
        for nxt, w in graph[node]:
            if t + w < dist[nxt]:
                dist[nxt] = t + w
                heapq.heappush(heap, (t + w, nxt))
    worst = 0
    for node in range(1, n + 1):
        if dist[node] == INF:
            return -1
        worst = max(worst, dist[node])
    return worst

Tuzaklar ve uç durumlar

Çoğu hata, bağlantıların yönünü göz ardı eder, bir düğüme sunulan ilk zamanı doğru kabul eder veya sinyalin hiç ulaşmadığı düğümleri hesaba katmaz.

Bağlantıları çift yönlü kabul etmek. [3, 1, 2] sinyali yalnızca 3'ten 1'e taşır; bu nedenle ikinci örnekte düğüm 3 sinyali hiç almaz.
Standart genişlik öncelikli arama kullanmak. Bu yöntem en az bağlantı içeren rotayı bulur, en hızlı olanı değil: ilk örnekte düğüm 2'ye, düğüm 3 üzerinden 3 yerine doğrudan bağlantı üzerinden 4 zamanını verir.
Bir düğüm yığına eklendiğinde onu kesin olarak işaretlemek, yığından çıkarıldığında değil. Bir düğüme sunulan ilk zaman her zaman en iyisi değildir; yalnızca yığından çıkarılan en küçük değer kesinleşir.
-1'i unutmak. Kontrol etmeden maksimumu almak ya sonsuz döndürür ya da sonlu en büyük zamanı bildirip sinyali hiç almamış düğümü gizler.
Düğümleri 0'dan saymak. Düğümler 1'den n'e kadar etiketlenir; bu nedenle dizileri n+1 boyutunda oluşturun ve kullanılmayan 0. yuvayı maksimum hesabının dışında bırakın.
Sonsuz değer nedeniyle taşma. Sonsuz değer en büyük int ise dist[u] + w, ulaşılmamış bir u için negatif bir sayıya sarılır. Ulaşılmamış düğümleri atlayın veya 10^9 gibi, taşma için pay bırakan bir değer kullanın.

Sıkça sorulan sorular4

Network Delay Time'ın zaman karmaşıklığı nedir?

Dijkstra algoritması ve ikili yığın kullanıldığında karmaşıklık O(E log E) olur; burada E, bağlantıların sayısıdır. Bu, O(E log n) ile aynıdır; çünkü E en fazla n² olabilir. Komşuluk listesi, süreler ve yığın O(n + E) alan kullanır. Bellman-Ford algoritması O(n · E) zaman ve O(n) alan gerektirir.

Dijkstra algoritması neden negatif olmayan ağırlıklara ihtiyaç duyar?

Dijkstra, geçici zamanı en küçük olan düğümü kesinleştirir ve ona bir daha bakmaz. Bu, ancak daha sonra bulunan hiçbir güzergâh daha kısa olamayacaksa güvenlidir; negatif olmayan ağırlıklarda, kesinleştirilmemiş bir düğümden geçen her güzergâhın maliyeti en az o düğümün zamanı kadardır. Negatif bir bağlantı bu mantığı bozar: daha maliyetli görünen bir düğümden geçen güzergâh yine de daha ucuz olabilir. Negatif ağırlıklar için Bellman-Ford kullanın.

Ağ Gecikme Süresi için neden BFS kullanmamalı?

BFS, düğümleri başlangıçtan kaç bağlantı uzakta olduklarına göre ziyaret eder; bu, yalnızca her bağlantı aynı süreyi aldığında varış zamanıyla örtüşür. Burada bağlantı süreleri farklı, dolayısıyla daha fazla bağlantı içeren bir rota daha önce varabilir. Tüm süreler eşit olsaydı BFS yeterli olurdu; süreler yalnızca 0 ve 1 olduğunda ise deque tabanlı 0-1 BFS işe yarar.

Network Delay Time problemini yığın kullanmadan çözebilir misin?

Evet. Sade bir dizi kullanan Dijkstra, en küçük süreyi bulmak için kesinleşmemiş tüm düğümleri tarar; bu işlem toplamda O(n²) maliyetlidir ve yığın gerektirmez. E'nin n²'ye yakın olduğu yoğun graflarda bu daha iyi bir seçimdir. Buradaki 3.000 düğüm ve 4.000 bağlantı içeren büyük testler gibi seyrek graflarda ise yığın sürümü çok daha az iş yapar.

Python

def networkDelayTime(times, n, k):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]
n = 4
k = 1

Beklenen

Network Delay Time

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her daha hızlı rotada yeniden ziyaret eden derinlik öncelikli arama

Bellman-Ford: her kenarı en fazla n-1 kez gevşet

Min yığın kullanan Dijkstra algoritması

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler