Network Delay Time
Bir ağda 1 ile n arasında etiketlenmiş n düğüm vardır. times[i] = [u, v, w] bağlantısı, sinyali yalnızca bu yönde, u düğümünden v düğümüne w zaman biriminde taşı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ı veya herhangi bir düğüme sinyal hiç ulaşmıyorsa -1 değerini döndür.
Fonksiyon
- timesinteger-2d-array
- yönlü bağlantıların her biri [u, v, w] biçiminde
- ninteger
- düğüm sayısı
- kinteger
- sinyali gönderen düğüm
- Döndürürinteger
- sinyali son düğümün aldığı zaman veya -1
Kısıtlar
2 ≤ n ≤ 30001 ≤ times.length ≤ 4000times[i].length = 31 ≤ u, v ≤ nveu ≠ v0 ≤ w ≤ 100- Hiçbir iki bağlantı hem aynı
uhem de aynıvdeğerine sahip değildir. 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
- Doğrudan bağlantı 2 numaralı düğüme 4. zamanda ulaşır, ancak 3 numaralı düğüm üzerinden geçen yol 1 + 2 = 3 sürede varır. 4 numaralı düğüm sinyali en son, 3 + 1 = 4 sürede alır.
- Girdi
- times = [[1, 2, 3], [3, 1, 2]]n = 3k = 1
- Çıktı
- -1
- Açıklama
- 2 numaralı düğüm sinyali 3. zamanda alır, ancak 3 numaralı düğüme bağlanan tek bağlantı 3'ten 1'e gider. 3 numaralı düğüm sinyali hiçbir zaman almaz, bu yüzden yanıt -1'dir.
- Girdi
- times = [[2, 1, 5], [2, 3, 0], [3, 1, 2]]n = 3k = 2
- Çıktı
- 2
- Açıklama
- 3. düğüme giden bağlantı 0 sürer, bu yüzden 3. düğüm sinyali 0 anında alır. Ardından 1. düğüm, doğrudan bağlantısının 5'inden daha erken, 0 + 2 = 2 anında sinyali alır.
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 duyduğu zamanı nasıl bulursun?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Bir düğüm,
kdüğümünden kendisine giden en hızlı rotanın süresi kadar zamanda sinyali alır. Bu nedenle yanıt, bu en hızlı sürelerin en büyüğüdür; herhangi bir düğüme giden hiçbir rota yoksa yanıt -1 olur.Hiçbir bağlantı negatif zaman almaz. Bu nedenle, zamanı henüz kesinleşmemiş düğümler arasında geçici zamanı en küçük olanın zamanı daha da kısalamaz: ona giden diğer tüm yollar, bu düğümlerden başka birinden geçer ve bu düğüme daha erken ulaşılamaz. Düğümleri varış sırasına göre kesinleştirin.
(time, node)çiftlerinden oluşan bir min-yığın tut. En küçüğünü çıkar, düğümün zaten daha küçük bir zamanı varsa atla ve zamanı iyileşen her komşuyu yığına ekle. Yığın boşaldığında en büyük zamanı al.
Çözüm
Her düğüm sinyali, k noktasından en hızlı rotasının uzunluğu kadar sürede alır; dolayısıyla bu, tek kaynaklı en kısa yolların ardından maksimum değerinin alınmasıdır veya bir düğüme giden rota yoksa -1'dir. Bağlantı süreleri hiçbir zaman negatif olmadığından, Dijkstra algoritması her düğümü bir kez kesinleştirir. Aşağıda E, 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
Şimdiye kadarki süreyi taşıyarak k'den başlayıp derinlik öncelikli ara ve her düğüme en hızlı varış zamanını kaydet. Bir düğüme kayıtlı varış zamanından daha erken ulaşmayan bir rota durur; daha erken ulaşan rota kaydı iyileştirir ve aramaya devam eder. En hızlı rota bir noktada kaydı iyileştireceği için her kayıt sonunda gerçek en hızlı zamana ulaşır.
Bir düğüm birçok kez iyileştirilebilir. Arka arkaya 18 kapı koy; her kapı çifti arasında maliyetsiz bir bağlantı ve 65,536, 32,768 ve böyle devam ederek 1'e kadar azalan maliyetlere sahip bir dolambaçlı yol olsun. Önce dolambaçlı yolları deneyen arama, son kapıya 131,072 farklı zamanda ulaşır ve her seferinde onun ardındaki her şeyi dolaşır: n cinsinden üstel iş.
Algoritma
- Her en iyi zamanı sonsuz olarak ayarla ve yığına
(k, 0)ekle. (node, t)öğesini yığından çıkar.t < best[node]değilse atla; değilsebest[node] = tolarak ayarla.nodenoktasından çıkan ve varış zamanıbest[next]değerinden önce olan her bağlantı için(next, t + w)öğesini ekle.- Yığın boşaldığında, en iyi zamanlardan herhangi biri sonsuzsa -1 döndür; aksi hâlde 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 worstBellman-Ford: her bağlantıyı en fazla n-1 kez gevşet
Sezgi
Her düğüm için, k için 0 olmak üzere, geçici bir dist zamanı tut. Bir u → v bağlantısını gevşetmek, daha küçük olması durumunda dist[v] değerini dist[u] + w değerine düşürür. Bellman-Ford her geçişte tüm bağlantıları gevşetir.
Bir düğüme giden en hızlı yolu ele alalım; örneğin k → a → b → v. İlk geçiş dist[a] değerini kesinleştirir, ikinci geçiş dist[b] değerini, üçüncü geçiş ise dist[v] değerini kesinleştirir. En hızlı yol hiçbir düğümü tekrarlamaz; bu nedenle en fazla n-1 bağlantı içerir ve n-1 geçiş her düğümün değerini kesinleştirir.
Her geçiş O(E) maliyetindedir. Uzak ucundan geriye doğru listelenmiş 3,000 düğümlü bir zincir, 4,000 bağlantı üzerinde 2,999 geçiş gerektirir: yaklaşık 12 milyon gevşetme.
Algoritma
dist[k] = 0olarak ayarla ve diğer tümdistdeğerlerini sonsuz yap.- En fazla n-1 kez tekrarla: her bağlantı
[u, v, w]için,dist[u] + w < dist[v]isedist[v] = dist[u] + wolarak ayarla. - Hiçbir şeyi değiştirmeyen bir geçişten sonra işlemi erken durdur.
- Herhangi bir
disthâlâ sonsuzsa -1 döndür; aksi takdirde en büyük olanı döndür.
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 worstMin-yığın ile Dijkstra algoritması
Sezgi
Henüz kesinleşmemiş düğümler arasında, geçici zamanı en küçük olan düğümün zamanı zaten kesindir. Bu düğüme giden başka herhangi bir yol, kesinleşmiş düğümlerden zamanı en az o kadar olan kesinleşmemiş bir düğüm üzerinden geçmek zorundadır ve sonraki bağlantılar yalnızca zaman ekler, çünkü hiçbir bağlantının değeri negatif değildir. Bu yüzden o düğümü kesinleştirir, bağlantılarını bir kez gevşetir ve işlemi tekrar edersin.
Bir min-heap en küçük zamanı bulur. Bir düğümün değeri iyileştiğinde yeni bir girdi eklersin ve eskisini olduğu yerde bırakırsın; zamanı dist değerinden büyük olan çıkarılmış bir girdi güncelliğini yitirmiştir, bu yüzden onu atlarsın. Her bağlantı en fazla bir girdi ekler, dolayısıyla heap en fazla E + 1 girdi tutar ve toplam karmaşıklık O(E log E) olur.
Algoritma
dist[k] = 0olarak ayarla, diğer tümdistdeğerlerini sonsuz yap ve(0, k)değerini bir min-yığına ekle.- En küçük
(t, node)değerini çıkar;t > dist[node]ise eski olduğu için atla. wsüresindeki hernode → nextbağlantısı için,t + w < dist[next]isedist[next] = t + wolarak ayarla ve(t + w, next)değerini ekle.- Yığın boşaldığında, herhangi bir
distsonsuzsa -1 döndür; aksi hâlde en büyük değeri 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
- Bağlantıları çift yönlü kabul etmek.
[3, 1, 2]sinyali yalnızca 3'ten 1'e taşır; bu nedenle 3 numaralı düğüm ikinci örnekte sinyali hiç duymaz. - Düz genişlik öncelikli arama kullanmak. Bu, en az bağlantı içeren yolu bulur: ilk örnekte 2 numaralı düğüme 3 yerine 4 zamanını verir.
- -1'i unutmak. Kontrol etmeden maksimum değeri almak sonsuz değer döndürür veya sinyali hiç duymayan düğümü gizler.
- En büyük int değerini sonsuzluk olarak kullanmak. Böylece ulaşılmamış bir
uiçindist[u] + wnegatif bir sayıya sarar; ulaşılmamış düğümleri atlayın veya 10^9 kullanın.
Sıkça sorulan sorular3
Ağ Gecikme Süresi'nin zaman karmaşıklığı nedir?
Dijkstra algoritması ve ikili yığınla karmaşıklık O(E log E) olur; burada E, bağlantıların sayısıdır. E en fazla n² olduğundan bu, O(E log n) değerine eşittir. Bellek karmaşıklığı O(n + E) olur. Bellman-Ford O(n · E) zaman alır.
Dijkstra algoritmasının negatif olmayan ağırlıklara ihtiyacı neden vardır?
Dijkstra, kesinleşmiş bir düğümü asla yeniden ziyaret etmez; bu ancak daha sonraki hiçbir rotanın daha kısa olamayacağı durumda güvenlidir. Süresi 2 olan A → B, süresi 3 olan A → C ve süresi -2 olan C → B bağlantıları olduğunda, B düğümünü 2'de kesinleştirir; ancak C üzerinden geçen rota bu düğüme 1'de ulaşır. Bellman-Ford negatif süreleri ele alır.
Ağ Gecikme Süresi problemini yığın kullanmadan çözebilir misin?
Evet. Düz bir dizi kullanan Dijkstra, en küçük süreyi bulmak için henüz kesinleşmemiş her düğümü tarar; bunun toplam maliyeti O(n²) olur. E'nin n²'ye yakın olduğu yoğun graflarda daha iyi performans gösterir. 3.000 düğüm ve 4.000 bağlantı gibi seyrek graflarda ise yığın sürümü çok daha az iş yapar.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def networkDelayTime(times, n, k):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]] n = 4 k = 1
Beklenen Çıktı
4