Network Delay Time
В сети есть n узлов, обозначенных числами от 1 до n. Связь times[i] = [u, v, w] передаёт сигнал от узла u к узлу v за w единиц времени только в этом направлении.
Сигнал отправляется из узла k в момент времени 0 и распространяется по всем доступным связям. Верните время, когда его получит последний узел, или -1, если какой-либо узел его так и не получит.
Функция
- timesinteger-2d-array
- ориентированные рёбра, каждое в виде [u, v, w]
- ninteger
- количество узлов
- kinteger
- узел, который отправляет сигнал
- Возвращаетinteger
- время, когда последний узел получает сигнал, или -1
Ограничения
2 ≤ n ≤ 30001 ≤ times.length ≤ 4000times[i].length = 31 ≤ u, v ≤ nиu ≠ v0 ≤ w ≤ 100- Никакие две ссылки не имеют одновременно одинаковые
uиv. 1 ≤ k ≤ n
Примеры
- Ввод
- times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
- Вывод
- 4
- Пояснение
- Сигнал по прямой связи достигает узла 2 за время 4, но по маршруту через узел 3 он приходит за 1 + 2 = 3. Узел 4 получает сигнал последним, через 3 + 1 = 4.
- Ввод
- times = [[1, 2, 3], [3, 1, 2]]n = 3k = 1
- Вывод
- -1
- Пояснение
- Узел 2 получает сигнал в момент времени 3, но единственная связь, соединяющая узел 3, ведёт от 3 к 1. Узел 3 так и не получает сигнал, поэтому ответ — -1.
- Ввод
- times = [[2, 1, 5], [2, 3, 0], [3, 1, 2]]n = 3k = 2
- Вывод
- 2
- Пояснение
- Путь до узла 3 занимает 0, поэтому узел 3 получает сигнал в момент времени 0. Затем узел 1 получает его в момент 0 + 2 = 2, раньше, чем через 5 по прямому каналу.
Дополнительный вопрос
Предположим, сигнал затухает, пройдя m связей. Как найти время, когда последний узел услышит его при этом ограничении?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Сигнал достигает узла за время, равное длине самого быстрого маршрута до него из
k. Поэтому ответ — наибольшее из этих времён, или -1, если до какого-либо узла вообще нет маршрута.Ни один переход не занимает отрицательное время. Поэтому среди узлов, для которых время ещё не окончательное, узел с наименьшим предварительным временем не может получить время ещё меньше: любой другой путь к нему проходит через другой такой узел, до которого нельзя добраться раньше. Фиксируйте узлы в порядке прибытия.
Храни кучу минимумов из пар
(time, node). Извлекай наименьшую пару, пропускай её, если для узла уже найдено меньшее время, и добавляй в кучу каждого соседа, для которого время улучшается. Когда куча опустеет, возьми наибольшее время.
Решение
Каждый узел получает сигнал через время, равное длине кратчайшего маршрута от k, поэтому сначала находим кратчайшие пути от одного источника, а затем максимум или -1, если до узла нет маршрута. Время прохождения по ребрам никогда не бывает отрицательным, поэтому алгоритм Дейкстры обрабатывает каждый узел один раз. Ниже E — это times.length.
Поиск в глубину, который повторно посещает узлы при каждом более быстром маршруте
Верно, но не успевает на самых больших тестах
Идея
Выполняй поиск в глубину от k, накапливая время в пути, и записывай самое быстрое время прибытия в каждый узел. Маршрут, достигающий узла не раньше, чем указанное в записи время, останавливается; более быстрый маршрут обновляет запись и продолжает поиск. Каждая запись в итоге содержит действительно самое быстрое время, поскольку самый быстрый маршрут в какой-то момент её улучшает.
Время прибытия в узел может улучшаться много раз. Расположи в ряд 18 ворот; каждую пару соедини бесплатной связью и обходным путём длительностью 65 536, 32 768 и так далее, вплоть до 1. Если сначала пробовать обходные пути, поиск достигнет последних ворот в 131 072 разных момента времени и каждый раз обойдёт всё, что за ними: объём работы экспоненциален по n.
Алгоритм
- Установите для каждого лучшего времени значение бесконечности и поместите
(k, 0)в стек. - Извлеките
(node, t). Пропустите его, еслиt < best[node]не выполняется; затем установитеbest[node] = t. - Поместите
(next, t + w)в стек для каждой связи изnode, время прибытия по которой меньшеbest[next]. - Когда стек опустеет, верните -1, если какое-либо лучшее время бесконечно; иначе верните наибольшее.
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Алгоритм Беллмана — Форда: выполняйте релаксацию каждого ребра до n-1 раз
Идея
Храните предварительное время dist для каждого узла, а для k задайте значение 0. При релаксации связи u → v значение dist[v] уменьшается до dist[u] + w, если оно меньше текущего. Алгоритм Беллмана — Форда релаксирует каждую связь на каждом проходе.
Возьмём кратчайший путь до некоторого узла, например k → a → b → v. На первом проходе окончательно определяется dist[a], на втором — dist[b], на третьем — dist[v]. Кратчайший путь никогда не проходит через один и тот же узел дважды, поэтому в нём не более n-1 связей, и за n-1 проходов определяются значения для всех узлов.
Каждый проход занимает O(E). Для цепочки из 3 000 узлов, перечисленных в обратном порядке — от дальнего конца, — потребуется 2 999 проходов по 4 000 связям: около 12 миллионов релаксаций.
Алгоритм
- Установи
dist[k] = 0, а все остальные значенияdist— равными бесконечности. - Повтори до n-1 раз: для каждой связи
[u, v, w], еслиdist[u] + w < dist[v], установиdist[v] = dist[u] + w. - Остановись раньше, если проход ничего не изменил.
- Верни -1, если какое-либо значение
distвсё ещё бесконечно, иначе — наибольшее значение.
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Алгоритм Дейкстры с минимальной кучей
Идея
Среди ещё не обработанных узлов узел с наименьшим предварительным временем уже имеет окончательное время. Любой другой маршрут к нему должен проходить из обработанных узлов через необработанный узел, время которого не меньше, а последующие рёбра только добавляют время, поскольку ни одно из них не имеет отрицательного веса. Поэтому фиксируйте время этого узла, один раз релаксируйте его рёбра и повторяйте.
Мини-куча находит наименьшее время. Когда расстояние до узла улучшается, добавляйте новую запись, а старую оставляйте на месте; извлечённая запись, время которой больше dist, устарела, поэтому пропустите её. Каждое ребро добавляет не более одной записи, поэтому куча содержит не более E + 1 записей, а общая сложность составляет O(E log E).
Алгоритм
- Установи
dist[k] = 0, всем остальным значениямdistприсвой бесконечность и добавь(0, k)в мин-кучу. - Извлеки наименьший
(t, node); еслиt > dist[node], пропусти его как устаревший. - Для каждой связи
node → nextсо временемw, еслиt + w < dist[next], установиdist[next] = t + wи добавь(t + w, next)в кучу. - Когда куча опустеет, верни -1, если какое-либо значение
distбесконечно; иначе верни наибольшее.
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
Ловушки и крайние случаи
- Считать ссылки двунаправленными.
[3, 1, 2]передаёт сигнал только от 3 к 1, поэтому во втором примере узел 3 его никогда не получает. - Использовать обычный поиск в ширину. Он находит путь с наименьшим количеством ссылок: в первом примере он даёт узлу 2 время 4 вместо 3.
- Забыть про -1. Если взять максимум без проверки, получится бесконечность или будет скрыт узел, который так и не получил сигнал.
- Использовать максимальное значение int как бесконечность. Тогда
dist[u] + wпереполняется до отрицательного числа для недостигнутогоu; пропускай недостигнутые узлы или используй 10^9.
Частые вопросы3
Какова временная сложность задачи Network Delay Time?
Алгоритм Дейкстры с бинарной кучей работает за O(E log E), где E — количество рёбер. Это равно O(E log n), поскольку E не превышает n². Для хранения требуется O(n + E) памяти. Алгоритм Беллмана — Форда работает за O(n · E) времени.
Почему алгоритму Дейкстры нужны неотрицательные веса?
Алгоритм Дейкстры никогда не возвращается к уже обработанному узлу, и это безопасно, только если никакой более поздний маршрут не может оказаться короче. При связях A → B со временем 2, A → C со временем 3 и C → B со временем -2 он обрабатывает B со временем 2, однако маршрут через C приводит к нему за 1. Алгоритм Беллмана — Форда работает с отрицательным временем.
Сможешь решить задачу Network Delay Time без кучи?
Да. Алгоритм Дейкстры с обычным массивом просматривает все узлы, для которых ещё не найден кратчайший путь, чтобы найти минимальное время; всего это требует O(n²). Он выигрывает на плотных графах, где E близко к n². На разреженных графах, например с 3 000 узлов и 4 000 рёбер, версия с кучей выполняет гораздо меньше работы.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def networkDelayTime(times, n, k):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргументы
times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]] n = 4 k = 1
Ожидаемый вывод
4