Задержка в сети и восстановление пути
Решите задачу о задержке в сети с помощью Дейкстры, восстановите фактический кратчайший путь по карте предшественников и обсудите двунаправленный BFS для больших графов
«Задержка в сети и восстановление пути» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Задача «Задержка в сети»
Задержка в сети (LeetCode 743): дана сеть из n узлов и ориентированных взвешенных рёбер, которые задают время распространения сигнала. Найдите минимальное время, за которое сигнал, отправленный из узла k, достигнет всех узлов. Если некоторый узел недостижим, верните -1. Это непосредственное применение алгоритма Дейкстры: ответом является максимальное расстояние кратчайшего пути от k до всех узлов.
Решение: алгоритм Дейкстры и максимум расстояний
Запустите алгоритм Дейкстры из исходной вершины k, чтобы найти dist[v] для всех узлов v. Ответом будет max(dist.values()). Если для некоторого dist[v] по-прежнему указано inf, этот узел недостижим — верните -1. Сигнал распространяется по всем путям одновременно, поэтому узким местом становится узел, до которого добираться дольше всего.
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
dist[k] = 0
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
ans = max(dist.values())
return ans if ans < float('inf') else -1
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) # 2Восстановление пути с помощью массива prev
Чтобы восстановить фактический кратчайший путь одновременно с вычислением расстояний, поддерживайте словарь prev, в котором для каждого узла записывается лучший предшественник. При каждом обновлении dist[v] устанавливайте prev[v] = u. После завершения алгоритма Дейкстры двигайтесь от конечной вершины назад по указателям prev, пока не достигнете исходной вершины, а затем разверните полученную последовательность, чтобы получить путь в прямом направлении.
import heapq
from collections import defaultdict
def shortest_path_with_reconstruction(times, n, src, dst):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
prev = {i: None for i in range(1, n+1)}
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
# Reconstruct path from src to dst
path, node = [], dst
while node is not None:
path.append(node)
node = prev[node]
return dist[dst], path[::-1]Двунаправленный BFS для больших невзвешенных графов
Для больших невзвешенных графов, когда требуется найти путь только между одной парой исходной и конечной вершин, двунаправленный BFS может быть значительно быстрее обычного BFS. Он одновременно запускает BFS из исходной и конечной вершин и останавливается, когда два фронта поиска встречаются. Практическое ускорение существенно, поскольку каждому фронту нужно исследовать только половину глубины графа: число исследованных узлов уменьшается с O(b^d) до O(2 × b^(d/2)), где b — коэффициент ветвления.
from collections import deque
def bidir_bfs(graph, src, dst):
if src == dst: return 0
front_q = deque([src]); front_visited = {src: 0}
back_q = deque([dst]); back_visited = {dst: 0}
def expand(queue, visited, other_visited):
node = queue.popleft()
for nxt in graph[node]:
if nxt not in visited:
visited[nxt] = visited[node] + 1
queue.append(nxt)
if nxt in other_visited:
return visited[nxt] + other_visited[nxt]
return -1
while front_q or back_q:
res = expand(front_q, front_visited, back_visited)
if res != -1: return res
res = expand(back_q, back_visited, front_visited)
if res != -1: return res
return -1Когда выбирать тот или иной алгоритм
Руководство по выбору: невзвешенный граф, одна пара вершин → BFS или двунаправленный BFS. Взвешенный граф, неотрицательные веса, одна исходная вершина → алгоритм Дейкстры. Взвешенный граф, возможно отрицательные веса, одна исходная вершина → алгоритм Беллмана—Форда. Все пары вершин → алгоритм Флойда—Уоршелла (при небольшом V) или V запусков алгоритма Дейкстры (для разреженного графа). Ограниченное число переходов → модифицированный алгоритм Беллмана—Форда с ограниченным числом проходов. Если Вы вслух объясняете это обоснование выбора на собеседовании, это демонстрирует зрелое алгоритмическое мышление.
Найдите город с наименьшим числом достижимых соседей (LeetCode 1334)
Даны города, соединённые взвешенными путями, и distanceThreshold. Найдите город, из которого в пределах заданного порога достижимо наименьшее число других городов (при равенстве предпочтение отдаётся городу с большим индексом). Решение: вычислите кратчайшие пути между всеми парами с помощью алгоритма Флойда—Уоршелла, затем для каждого города подсчитайте, сколько других городов достижимо в пределах порога. Верните город с минимальным количеством таких городов (при равенстве — с максимальным индексом).
def findTheCity(n, edges, distanceThreshold):
INF = float('inf')
dist = [[INF]*n for _ in range(n)]
for i in range(n): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = dist[v][u] = w
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
best_city, best_count = -1, n
for city in range(n):
count = sum(1 for j in range(n) if j != city and dist[city][j] <= distanceThreshold)
if count <= best_count:
best_count = count
best_city = city
return best_city
print(findTheCity(4,[[0,1,3],[1,2,1],[1,3,4],[2,3,1]],4)) # 3Путь во взвешенном DAG
Для ориентированного ацикличного графа (DAG) кратчайшие (или длиннейшие) пути можно найти с помощью топологической сортировки и релаксации за O(V+E) — это быстрее алгоритма Дейкстры. Обрабатывайте узлы в топологическом порядке; при обработке узла u выполняйте релаксацию всех исходящих рёбер. Для поиска длиннейших путей (что полезно при планировании проектов и поиске критического пути) инвертируйте веса или замените min на max.
from collections import deque
def dag_shortest_path(V, edges, source):
graph = [[] for _ in range(V)]
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
# Topological sort (Kahn's)
queue = deque(i for i in range(V) if in_degree[i] == 0)
topo = []
while queue:
node = queue.popleft(); topo.append(node)
for nxt, _ in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
# Relax in topological order
dist = [float('inf')] * V
dist[source] = 0
for u in topo:
if dist[u] != float('inf'):
for v, w in graph[u]:
dist[v] = min(dist[v], dist[u] + w)
return distКратчайший путь в матрице с препятствиями
Распространённый вариант задачи на собеседовании: найдите кратчайший путь в двумерной сетке из верхнего левого угла в нижний правый, если некоторые клетки могут быть заблокированы. Это задача о невзвешенном BFS (каждый шаг стоит 1). Используйте BFS с перемещением в четырёх направлениях и отмечайте клетки посещёнными при добавлении в очередь (а не при извлечении), чтобы избежать повторного посещения. Если через препятствия можно проходить, заплатив определённую стоимость, применяйте алгоритм Дейкстры к двумерной сетке, рассматривая её как взвешенный граф.
from collections import deque
def shortest_path_binary_matrix(grid):
n = len(grid)
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return -1
queue = deque([(0, 0, 1)]) # (row, col, distance)
visited = {(0, 0)}
dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
while queue:
r, c, d = queue.popleft()
if r == n-1 and c == n-1:
return d
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<n and 0<=nc<n and grid[nr][nc]==0 and (nr,nc) not in visited:
visited.add((nr,nc))
queue.append((nr, nc, d+1))
return -1
print(shortest_path_binary_matrix([[0,0,0],[1,1,0],[1,1,0]])) # 4BFS из нескольких источников
Если существует несколько исходных точек (например, несколько «ворот» в сетке или несколько источников на карте), выполните BFS из нескольких источников: одновременно добавьте все источники в очередь с расстоянием 0. За один проход BFS это вычисляет кратчайшее расстояние от ближайшего источника до каждой клетки. Такой метод избавляет от необходимости отдельно запускать BFS из каждого источника и имеет общую сложность O(V+E).
Итоги выбора алгоритма
Краткое дерево решений: одна исходная вершина, неотрицательные веса → алгоритм Дейкстры O((V+E) log V). Одна исходная вершина, отрицательные веса → алгоритм Беллмана—Форда O(VE). Все пары вершин, небольшое V → алгоритм Флойда—Уоршелла O(V³). DAG, любые веса → топологическая сортировка + релаксация O(V+E). Невзвешенный граф → BFS O(V+E). Пути в сетке → BFS (для невзвешенного графа) или алгоритм Дейкстры с кучей (для взвешенного графа). Запомните эту таблицу — она поможет отвечать на дополнительные вопросы на любом собеседовании по поиску кратчайших путей.
Поиск пути в задачах на собеседовании
Во многих задачах на собеседовании требуется найти сам путь, а не только его стоимость. Всегда уточняйте: нужен ли Вам путь или достаточно расстояния? Если путь нужен, создайте словарь prev в самом начале. Распространённые ошибки: забыть инициализировать prev[source] = None как конечное условие и перепутать порядок восстановления (двигаться от конечной вершины к исходной, а затем развернуть последовательность). Потренируйтесь восстанавливать пути на примерах с 3–4 узлами, прежде чем переходить к более крупным задачам.
Быстрая проверка
Проверьте своё понимание концепций курса «Структуры данных и алгоритмы — подготовка к техническому собеседованию», рассмотренных в этом уроке.
Итоги урока
В этом уроке Вы узнали: ответом для задачи «Задержка в сети» после алгоритма Дейкстры является max(dist.values()), для восстановления пути используется массив prev, обновляемый при каждом улучшении dist[v], а двунаправленный BFS может вдвое сократить пространство поиска для поиска кратчайшего пути между одной парой вершин в невзвешенном графе. Далее мы перейдём к упорядочиванию графов и алгоритму Кана для топологической сортировки.
Часто задаваемые вопросы
Урок «Задержка в сети и восстановление пути» бесплатный?
Да — полный текст урока «Задержка в сети и восстановление пути» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Задержка в сети и восстановление пути»?
Решите задачу о задержке в сети с помощью Дейкстры, восстановите фактический кратчайший путь по карте предшественников и обсудите двунаправленный BFS для больших графов Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Задержка в сети и восстановление пути»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Алгоритм Дейкстры с очередью с приоритетами
- Беллман—Форд и отрицательные циклы
- Флойд—Уоршелл: кратчайшие пути между всеми парами
- Задержка в сети и восстановление пути