Network Delay Time

Q: Какова временная сложность задачи «Время задержки сети»?

С алгоритмом Дейкстры и бинарной кучей это O(E log E), где E — количество связей. Это то же самое, что O(E log n), поскольку E не превышает n². Список смежности, массив времен и куча занимают O(n + E) памяти. Алгоритм Беллмана — Форда работает за O(n · E) времени и использует O(n) памяти.

Q: Почему алгоритму Дейкстры нужны неотрицательные веса?

Алгоритм Дейкстры выбирает вершину с наименьшим предварительным временем и больше к ней не возвращается. Это безопасно только в том случае, если никакой более поздний маршрут не окажется короче, а при неотрицательных весах любой маршрут через ещё не выбранную вершину имеет стоимость не меньше времени этой вершины. Отрицательное ребро нарушает это рассуждение: маршрут через вершину, которая казалась более дорогой, всё же может оказаться дешевле. Для отрицательных весов используйте алгоритм Беллмана — Форда.

Q: Почему бы не использовать BFS для задачи Network Delay Time?

BFS посещает узлы в порядке количества переходов от начала, что соответствует времени прибытия, только если каждый переход занимает одинаковое время. Здесь время переходов различается, поэтому маршрут с большим количеством переходов может привести к месту назначения быстрее. Если бы время всех переходов было одинаковым, BFS было бы достаточно, а при времени переходов только 0 и 1 работает 0-1 BFS на основе дека.

Q: Можешь решить задачу Network Delay Time без кучи?

Да. Алгоритм Дейкстры с обычным массивом просматривает все непосещённые узлы, чтобы найти узел с наименьшим временем; в сумме это требует O(n²) операций и не требует кучи. Это лучший выбор для плотных графов, где E близко к n². На разреженных графах, как в больших тестах здесь с 3,000 узлами и 4,000 рёбрами, версия с кучей выполняет гораздо меньше работы.

СреднеКратчайшие пути Графы Куча

+10

Сеть содержит n узлов с метками от 1 до n. Связи заданы списком times, где times[i] = [u, v, w] означает, что сигнал, отправленный из узла u, достигает узла v через w единиц времени. Связи работают только в одном направлении.

Сигнал выходит из узла k в момент времени 0 и проходит по всем доступным ему связям. Верните время, когда его получит последний узел, или -1, если какой-либо узел его так и не получит.

Функция

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

timesinteger-2d-array: ориентированные рёбра, каждое в виде [u, v, w]
ninteger: количество узлов
kinteger: узел, который отправляет сигнал
Возвращаетinteger: время, когда последний узел получает сигнал, или -1

Ограничения

2 ≤ n ≤ 3000
1 ≤ times.length ≤ 4000
times[i].length = 3
1 ≤ u, v ≤ n и u ≠ v
0 ≤ w ≤ 100
Нет двух ссылок, у которых совпадают и u, и v.
1 ≤ k ≤ n

Примеры

Ввод: times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
Вывод: 4
Пояснение: Узел 3 получает сигнал в момент времени 1. Узел 2 мог бы получить его в момент времени 4 по прямому каналу, но по маршруту через узел 3 сигнал поступает в момент 1 + 2 = 3, а узел 4 получает его в момент 3 + 1 = 4. Последним сигнал получает узел 4, в момент времени 4.

+16 скрытых тестов при отправке

Дополнительный вопрос

Предположим, сигнал затухает после прохождения m звеньев. Как найти время, когда последний узел услышит его при таком ограничении?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Каждый узел получает сигнал за время, равное длине его самого быстрого маршрута от k, поэтому задача сводится к поиску кратчайших путей от одного источника в ориентированном графе, а затем — к нахождению максимума. Ответ — наибольшее время среди кратчайших путей или -1, если до какого-либо узла нет маршрута. Время прохождения по рёбрам никогда не бывает отрицательным, поэтому алгоритм Дейкстры может окончательно обрабатывать каждый узел один раз, в порядке прибытия сигнала, используя min-heap. Ниже E — количество рёбер, times.length.

Поиск в глубину, который повторно посещает вершину при каждом более быстром маршруте

Верно, но не успевает на самых больших тестах

Идея

Начните поиск в узле k со временем 0 и пройдите по каждой ссылке, учитывая прошедшее время. Записывайте для каждого узла самое быстрое время прибытия. Если поиск достигает узла не раньше, чем указано в его записи, остановитесь: всё, что этот маршрут мог бы предложить дальше, уже предложил более быстрый маршрут. Если поиск достигает узла раньше, запись обновляется, и всё, что находится за этим узлом, тоже может улучшиться, поэтому поиск продолжается от него.

Это всегда правильно. Поиск останавливается только тогда, когда ни один маршрут не улучшает ни одну запись, а самый быстрый маршрут до каждого узла в какой-то момент улучшает запись этого узла, поэтому в каждой записи в итоге оказывается действительно самое быстрое время.

Проблема в том, сколько раз может улучшиться запись узла. Поиск в глубину проходит по первой встреченной ссылке до самого конца, поэтому он может достичь узла по медленному маршруту, затем по немного более быстрому, а потом снова по более быстрому и каждый раз обходить всё, что находится за этим узлом. Представьте 18 ворот в ряд. Между каждой парой ворот можно пройти по бесплатной ссылке или выбрать объезд — цепочку ссылок, время прохождения которых в сумме составляет 65,536, 32,768 и так далее, вплоть до 1. Сначала пробуя объезды, поиск достигает последних ворот в 131,072 разных момента времени, каждый раз раньше предыдущего, и каждый раз проходит 1,700 узлов за ними: около 220 миллионов шагов. Два больших теста устроены таким образом: в одном каждый объезд указан перед бесплатной ссылкой, а в другом — после неё, поэтому поиск обязательно наткнётся на один из них независимо от того, в каком порядке он проверяет ссылки.

Алгоритм

Постройте список смежности: для каждого узла укажите исходящие из него связи и время их прохождения.
Установите для каждого узла лучшее время, равное бесконечности, и поместите (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 для каждого узла: 0 для k, бесконечность для остальных. Релаксация связи u → v со временем w означает: если dist[u] + w меньше dist[v], то эта связь предлагает более быстрый путь к v, поэтому уменьши dist[v] до этого значения. Bellman-Ford проходит по всему списку и релаксирует каждую связь за один проход.

Почему в итоге получаются правильные времена? Возьмём самый быстрый маршрут до некоторого узла, например k → a → b → v. В первом проходе релаксируется k → a, поскольку dist[k] уже равен 0, поэтому после него dist[a] становится окончательным. Во втором проходе окончательным становится dist[b], в третьем — dist[v]. Для самого быстрого маршрута никогда не нужно посещать один узел дважды, поскольку цикл не может иметь отрицательное время, поэтому в нём не более n-1 связей, и n-1 проходов достаточно, чтобы зафиксировать значения для всех узлов. Если проход ничего не изменил, это доказывает, что последующие проходы тоже ничего не изменят, поэтому можно остановиться.

Каждый проход требует O(E), поэтому в худшем случае сложность составляет O(n · E). Порядок списка определяет, насколько всё замедлится: если связи одного длинного маршрута перечислены от дальнего конца к началу, каждый проход фиксирует значение ещё для одного узла. Один большой тест устроен именно так: цепочка из 3,000 узлов, перечисленная в обратном порядке, требует 2,999 проходов по 4,000 связям — около 12 миллионов релаксаций. При таком размере этот алгоритм всё ещё работает достаточно быстро, но объём вычислений растёт пропорционально n, умноженному на E. Сильная сторона Bellman-Ford в другом: он остаётся корректным, даже если время некоторых связей отрицательное, тогда как Dijkstra не справляется.

Алгоритм

Установи 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

Алгоритм Дейкстры с минимальной кучей

Идея

Bellman-Ford выполняет лишние проходы, потому что релаксирует рёбра, выходящие из узлов, для которых время ещё не окончательное, и ему приходится возвращаться к ним. Алгоритм Дейкстры релаксирует рёбра каждого узла ровно один раз — в тот момент, когда его время становится окончательным. Вопрос в том, как определить этот момент.

Ответ — жадное правило: среди узлов, для которых окончательное время ещё не установлено, узел с наименьшим предварительным временем уже имеет окончательное время. Любой другой путь к нему должен в какой-то момент выйти из уже обработанных узлов через ещё не обработанный узел, время которого не меньше, а последующие рёбра могут только увеличить время, поскольку ни одно из них не имеет отрицательного веса. Поэтому окончательно фиксируем время этого узла, релаксируем его рёбра и повторяем. В первом примере время узла 1 становится окончательным и равным 0, после чего ему назначаются предварительные времена 4 для узла 2 и 1 для узла 3. У узла 3 время наименьшее, поэтому оно становится окончательным и равным 1, а время узла 2 уменьшается до 3. Время узла 2 становится окончательным и равным 3, после чего ему назначается предварительное время 4 для узла 4, которое становится окончательным последним. Ответ — 4.

Мини-куча позволяет быстро находить наименьшее предварительное время. Добавляй (time, node) в кучу каждый раз, когда время узла улучшается, а старую запись оставляй в куче вместо того, чтобы искать её. Когда старая запись позже извлечётся, её время будет больше текущего времени узла, поэтому пропусти её. Каждое ребро добавляет не более одной записи, поэтому в куче никогда не бывает больше E + 1 записей, а каждая операция добавления или извлечения занимает O(log E). В итоге получается O(E log E), а для списка смежности, времён и кучи требуется O(n + E) памяти.

Именно неотрицательные времена делают жадное правило надёжным. Рассмотрим рёбра A → B со временем 2, A → C со временем 3 и C → B со временем -2. Алгоритм Дейкстры фиксирует время узла B равным 2, хотя путь через C достигает его за 1. Сигнал не может прибыть раньше, чем он был отправлен, поэтому каждое время здесь не меньше 0 и правило выполняется.

Алгоритм

Построй список смежности из пар (next, w) для каждого узла.
Установи dist[k] = 0, для всех остальных значений dist — бесконечность и добавь (0, k) в min-heap.
Извлеки наименьшую пару (t, node). Если t > dist[node], запись устарела: пропусти её.
В противном случае t — окончательное значение. Для каждой связи от 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 через узел 3.
Помечать узел как окончательный при добавлении в очередь, а не при извлечении из неё. Первое предложенное для узла значение времени не всегда является наилучшим; окончательным считается только наименьшая запись, извлечённая из кучи.
Забывать про -1. Если взять максимум, ничего не проверив, результатом будет либо бесконечность, либо наибольшее конечное время, при этом узел, который так и не получил сигнал, будет проигнорирован.
Нумеровать узлы с 0. Узлы пронумерованы от 1 до n, поэтому задайте размер массивов n+1, а неиспользуемый слот 0 исключите из поиска максимума.
Переполнение при использовании бесконечности. Если бесконечность — это наибольшее значение типа int, то dist[u] + w переполнится и станет отрицательным числом для недостигнутого узла u. Пропускайте недостигнутые узлы или используйте значение, например 10^9, оставляющее запас.

Частые вопросы4

Какова временная сложность задачи «Время задержки сети»?

С алгоритмом Дейкстры и бинарной кучей это O(E log E), где E — количество связей. Это то же самое, что O(E log n), поскольку E не превышает n². Список смежности, массив времен и куча занимают O(n + E) памяти. Алгоритм Беллмана — Форда работает за O(n · E) времени и использует O(n) памяти.

Почему алгоритму Дейкстры нужны неотрицательные веса?

Алгоритм Дейкстры выбирает вершину с наименьшим предварительным временем и больше к ней не возвращается. Это безопасно только в том случае, если никакой более поздний маршрут не окажется короче, а при неотрицательных весах любой маршрут через ещё не выбранную вершину имеет стоимость не меньше времени этой вершины. Отрицательное ребро нарушает это рассуждение: маршрут через вершину, которая казалась более дорогой, всё же может оказаться дешевле. Для отрицательных весов используйте алгоритм Беллмана — Форда.

Почему бы не использовать BFS для задачи Network Delay Time?

BFS посещает узлы в порядке количества переходов от начала, что соответствует времени прибытия, только если каждый переход занимает одинаковое время. Здесь время переходов различается, поэтому маршрут с большим количеством переходов может привести к месту назначения быстрее. Если бы время всех переходов было одинаковым, BFS было бы достаточно, а при времени переходов только 0 и 1 работает 0-1 BFS на основе дека.

Можешь решить задачу Network Delay Time без кучи?

Да. Алгоритм Дейкстры с обычным массивом просматривает все непосещённые узлы, чтобы найти узел с наименьшим временем; в сумме это требует O(n²) операций и не требует кучи. Это лучший выбор для плотных графов, где E близко к n². На разреженных графах, как в больших тестах здесь с 3,000 узлами и 4,000 рёбрами, версия с кучей выполняет гораздо меньше работы.

Python

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

Ожидается

Network Delay Time

Функция

Ограничения

Примеры

Подсказки

Решение

Поиск в глубину, который повторно посещает вершину при каждом более быстром маршруте

Алгоритм Беллмана — Форда: ослабляйте каждое ребро до n-1 раз

Алгоритм Дейкстры с минимальной кучей

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи