Network Delay Time
Sieć ma n węzłów oznaczonych od 1 do n. Łącze times[i] = [u, v, w] przenosi sygnał z węzła u do węzła v w czasie w, tylko w tym kierunku.
Sygnał opuszcza węzeł k w chwili 0 i rozchodzi się wszystkimi łączami, którymi może. Zwróć czas, w którym odbierze go ostatni węzeł, lub -1, jeśli sygnał nigdy nie dotrze do któregoś węzła.
Funkcja
- timesinteger-2d-array
- skierowane krawędzie, każda w postaci [u, v, w]
- ninteger
- liczba węzłów
- kinteger
- węzeł, który wysyła sygnał
- Zwracainteger
- czas, w którym ostatni węzeł odbiera sygnał, lub -1
Ograniczenia
2 ≤ n ≤ 30001 ≤ times.length ≤ 4000times[i].length = 31 ≤ u, v ≤ norazu ≠ v0 ≤ w ≤ 100- Żadne dwie krawędzie nie mają jednocześnie takich samych
uiv. 1 ≤ k ≤ n
Przykłady
- Wejście
- times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
- Wyjście
- 4
- Wyjaśnienie
- Bezpośrednie połączenie dociera do węzła 2 w czasie 4, ale trasa przez węzeł 3 dociera po 1 + 2 = 3. Węzeł 4 odbiera sygnał jako ostatni, po 3 + 1 = 4.
- Wejście
- times = [[1, 2, 3], [3, 1, 2]]n = 3k = 1
- Wyjście
- -1
- Wyjaśnienie
- Węzeł 2 odbiera sygnał w chwili 3, ale jedyne połączenie z węzłem 3 prowadzi od 3 do 1. Węzeł 3 nigdy go nie odbiera, więc odpowiedź to -1.
- Wejście
- times = [[2, 1, 5], [2, 3, 0], [3, 1, 2]]n = 3k = 2
- Wyjście
- 2
- Wyjaśnienie
- Łącze do węzła 3 ma wartość 0, więc węzeł 3 odbiera sygnał w chwili 0. Następnie węzeł 1 odbiera go w chwili 0 + 2 = 2, wcześniej niż po upływie 5 z jego bezpośredniego łącza.
Pytanie dodatkowe
Załóżmy, że sygnał zanika po przejściu przez m łączy. Jak znaleźć czas, w którym ostatni węzeł go usłyszy, nie przekraczając tego limitu?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Węzeł otrzymuje sygnał po czasie równym długości najszybszej trasy do niego z
k. Zatem odpowiedzią jest największy z tych najszybszych czasów albo -1, jeśli do któregoś węzła nie ma żadnej trasy.Żadne połączenie nie zajmuje ujemnego czasu. Zatem spośród węzłów, których czas nie jest jeszcze ostateczny, ten z najmniejszym czasem tymczasowym nie może zostać osiągnięty szybciej: każda inna trasa do niego prowadzi przez inny z tych węzłów, do którego dociera się nie wcześniej. Ustalaj węzły w kolejności przybycia.
Przechowuj kopiec minimalny par
(time, node). Zdejmuj najmniejszy element, pomiń go, jeśli węzeł ma już mniejszy czas, i dodaj każdego sąsiada, którego czas ulegnie poprawie. Gdy kopiec będzie pusty, weź największy czas.
Rozwiązanie
Każdy węzeł odbiera sygnał po czasie równym długości jego najszybszej trasy z k, więc jest to problem najkrótszych ścieżek z jednego źródła, po którym bierzemy maksimum, albo -1, gdy do danego węzła nie prowadzi żadna trasa. Czasy połączeń nigdy nie są ujemne, więc algorytm Dijkstry ustala każdy węzeł tylko raz. Poniżej E to times.length.
Przeszukiwanie w głąb, które odwiedza ponownie każdy szybszy szlak
Poprawne, ale nie kończy się na największych testach
Intuicja
Przeszukuj w głąb od k, przenosząc dotychczasowy czas i zapisując najszybszy czas dotarcia do każdego węzła. Trasa, która dociera do węzła nie wcześniej niż zapisany czas, kończy się; szybsza trasa poprawia zapis i kontynuuje przeszukiwanie. Każdy zapis kończy się na rzeczywiście najszybszym czasie, ponieważ najszybsza trasa w pewnym momencie go poprawia.
Czas dotarcia do węzła może zostać poprawiony wiele razy. Ustaw 18 bramek w rzędzie, łącząc każdą parę darmowym połączeniem oraz objazdem o długości 65,536, 32,768 i tak dalej, aż do 1. Jeśli najpierw próbujesz objazdów, przeszukiwanie dociera do ostatniej bramki przy 131,072 różnych czasach i za każdym razem przechodzi przez wszystko, co znajduje się za nią: praca wykładnicza względem n.
Algorytm
- Ustaw każdy najlepszy czas na nieskończoność i umieść
(k, 0)na stosie. - Zdejmij
(node, t). Pomiń go, chyba żet < best[node]; następnie ustawbest[node] = t. - Umieść
(next, t + w)na stosie dla każdego połączenia znode, którego czas dotarcia jest lepszy niżbest[next]. - Gdy stos będzie pusty, zwróć -1, jeśli którykolwiek najlepszy czas jest nieskończony; w przeciwnym razie zwróć największy.
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: relaksuj każdą krawędź do n-1 razy
Intuicja
Przechowuj wstępną odległość dist dla każdego węzła, a dla k ustaw 0. Rozluźnienie połączenia u → v zmniejsza dist[v] do dist[u] + w, jeśli ta wartość jest mniejsza. Bellman-Ford rozluźnia każde połączenie podczas każdego przebiegu.
Weź najszybszą trasę do węzła, na przykład k → a → b → v. Pierwszy przebieg ustala ostateczną wartość dist[a], drugi — dist[b], a trzeci — dist[v]. Najszybsza trasa nigdy nie przechodzi ponownie przez ten sam węzeł, więc ma co najwyżej n-1 połączeń, a n-1 przebiegów wystarcza, by ustalić wartości dla każdego węzła.
Każdy przebieg kosztuje O(E). Łańcuch złożony z 3,000 węzłów, wymienionych od najdalszego końca wstecz, wymaga 2,999 przebiegów przez 4,000 połączeń: około 12 milionów operacji rozluźniania.
Algorytm
- Ustaw
dist[k] = 0, a każdą inną wartośćdistna nieskończoność. - Powtórz do n-1 razy: dla każdego łącza
[u, v, w], jeślidist[u] + w < dist[v], ustawdist[v] = dist[u] + w. - Zakończ wcześniej, jeśli podczas przebiegu nic się nie zmieni.
- Zwróć -1, jeśli którakolwiek wartość
distnadal jest nieskończona; w przeciwnym razie zwróć największą z nich.
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 worstAlgorytm Dijkstry z kopcem minimalnym
Intuicja
Spośród węzłów, które nie zostały jeszcze ustalone, ten o najmniejszym wstępnym czasie jest już ostateczny. Każda inna trasa do niego musi prowadzić przez nieustalony węzeł, którego czas jest co najmniej tak duży, a kolejne krawędzie tylko dodają czas, ponieważ żadna z nich nie ma wartości ujemnej. Dlatego ustalasz ten węzeł, raz relaksujesz jego krawędzie i powtarzasz.
Kopiec minimum znajduje najmniejszy czas. Gdy czas dla węzła się poprawi, dodaj nowy wpis i pozostaw stary na miejscu; zdjęty wpis, którego czas jest większy niż dist, jest nieaktualny, więc go pomijasz. Każda krawędź dodaje najwyżej jeden wpis, więc kopiec zawiera najwyżej E + 1 wpisów, a całkowita złożoność wynosi O(E log E).
Algorytm
- Ustaw
dist[k] = 0, każdą pozostałą wartośćdistna nieskończoność i umieść(0, k)w kopcu minimum. - Wyjmij najmniejszą parę
(t, node); jeślit > dist[node], pomiń ją jako nieaktualną. - Dla każdego połączenia
node → nexto czasiew, jeślit + w < dist[next], ustawdist[next] = t + wi umieść(t + w, next)w kopcu. - Gdy kopiec będzie pusty, zwróć -1, jeśli którakolwiek wartość
distjest nieskończona; w przeciwnym razie zwróć największą wartość.
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
Pułapki i przypadki brzegowe
- Traktowanie łączy jako dwukierunkowych.
[3, 1, 2]przekazuje sygnał tylko z 3 do 1, więc w drugim przykładzie węzeł 3 nigdy go nie odbiera. - Używanie zwykłego przeszukiwania wszerz. Znajduje trasę z najmniejszą liczbą łączy: w pierwszym przykładzie daje węzłowi 2 czas 4 zamiast 3.
- Zapominanie o -1. Zwrócenie maksimum bez sprawdzenia daje nieskończoność lub ukrywa węzeł, który nigdy nie odebrał sygnału.
- Używanie największej wartości typu int jako nieskończoności.
dist[u] + wprzepełnia się wtedy do liczby ujemnej dla nieosiągniętegou; pomijaj nieosiągnięte węzły lub użyj 10^9.
Najczęstsze pytania3
Jaka jest złożoność czasowa problemu czasu opóźnienia sieci?
W przypadku algorytmu Dijkstry z kopcem binarnym złożoność wynosi O(E log E), gdzie E to liczba krawędzi. Jest to równe O(E log n), ponieważ E jest co najwyżej równe n². Złożoność pamięciowa wynosi O(n + E). Algorytm Bellmana-Forda działa w czasie O(n · E).
Dlaczego algorytm Dijkstry wymaga nieujemnych wag?
Dijkstra nigdy nie odwiedza ponownie ustalonego węzła, co jest bezpieczne tylko wtedy, gdy żadna późniejsza trasa nie może być krótsza. Przy połączeniach A → B o czasie 2, A → C o czasie 3 i C → B o czasie -2 algorytm ustala odległość do B na 2, ale trasa przez C dociera do niego w czasie 1. Bellman-Ford obsługuje ujemne czasy.
Czy potrafisz rozwiązać problem czasu opóźnienia sieci bez kopca?
Tak. Algorytm Dijkstry ze zwykłą tablicą przegląda każdy nieustalony wierzchołek, aby znaleźć najmniejszy czas, co łącznie kosztuje O(n²). Sprawdza się lepiej w gęstych grafach, gdzie E jest bliskie n². W rzadkich grafach, takich jak grafy z 3 000 wierzchołkami i 4 000 krawędziami, wersja z kopcem wykonuje znacznie mniej pracy.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def networkDelayTime(times, n, k):
# Wpisz kod tutajTest #1
Test #2
Test #3
Argumenty
times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]] n = 4 k = 1
Oczekiwany wynik
4