Opóźnienie sieci i odtwarzanie ścieżki
Rozwiązywać problem network-delay-time algorytmem Dijkstry, odtwarzać rzeczywistą najkrótszą ścieżkę za pomocą mapy poprzedników oraz omawiać dwukierunkowe BFS dla dużych grafów
Opóźnienie sieci i odtwarzanie ścieżki to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Problem Network Delay Time
Network Delay Time (LeetCode 743): mając sieć złożoną z n węzłów oraz skierowane krawędzie z wagami reprezentującymi czas przesyłania sygnału, należy znaleźć minimalny czas, po którym sygnał wysłany z węzła k dotrze do wszystkich węzłów. Jeśli któryś węzeł jest nieosiągalny, należy zwrócić -1. Jest to bezpośrednie zastosowanie algorytmu Dijkstry: wynikiem jest największa odległość najkrótszej ścieżki od k do dowolnego węzła.
Rozwiązanie: algorytm Dijkstry i maksimum odległości
Uruchom algorytm Dijkstry ze źródła k, aby znaleźć dist[v] dla każdego węzła v. Wynikiem jest max(dist.values()). Jeśli dla któregoś dist[v] nadal wynosi inf, ten węzeł jest nieosiągalny — należy zwrócić -1. Sygnał przemieszcza się wszystkimi ścieżkami jednocześnie, więc ograniczeniem jest węzeł, do którego dotarcie zajmuje najwięcej czasu.
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)) # 2Odtwarzanie ścieżki za pomocą tablicy prev
Aby wraz z odległościami wyznaczyć także rzeczywistą najkrótszą ścieżkę, należy prowadzić słownik prev, który zapisuje najlepszego poprzednika każdego węzła. Za każdym razem, gdy aktualizujemy dist[v], ustawiamy prev[v] = u. Po zakończeniu działania algorytmu Dijkstry należy prześledzić wskaźniki prev wstecz od miejsca docelowego aż do źródła, a następnie odwrócić otrzymaną kolejność, aby uzyskać ścieżkę od źródła do celu.
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]Dwukierunkowy BFS dla dużych grafów nieważonych
W przypadku dużych grafów nieważonych, gdy potrzebna jest tylko jedna para źródło–cel, dwukierunkowy BFS może być znacznie szybszy od standardowego BFS. Algorytm jednocześnie uruchamia BFS ze źródła i z miejsca docelowego, kończąc działanie, gdy oba fronty się spotkają. Przyspieszenie w praktyce jest znaczące, ponieważ każdy front musi zbadać tylko połowę głębokości grafu — liczba odwiedzanych węzłów zmniejsza się z O(b^d) do O(2 × b^(d/2)), gdzie b oznacza współczynnik rozgałęzienia.
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 -1Kiedy wybrać poszczególny algorytm
Wskazówki dotyczące wyboru: graf nieważony, jedna para → BFS lub dwukierunkowy BFS. Graf ważony, nieujemne wagi, jedno źródło → algorytm Dijkstry. Graf ważony, możliwe ujemne wagi, jedno źródło → algorytm Bellmana-Forda. Wszystkie pary → Floyd-Warshall (dla małego V) lub V × Dijkstra (dla grafu rzadkiego). Ograniczona liczba przejść → zmodyfikowany algorytm Bellmana-Forda z ograniczoną liczbą przebiegów. Wypowiedzenie takiego uzasadnienia wyboru podczas rozmowy kwalifikacyjnej świadczy o dojrzałości algorytmicznej.
Znajdź miasto z najmniejszą liczbą osiągalnych sąsiadów (LeetCode 1334)
Mając miasta połączone ścieżkami z wagami oraz wartość distanceThreshold, należy znaleźć miasto, z którego w zasięgu tego progu można dotrzeć do najmniejszej liczby innych miast (w przypadku remisu należy wybrać miasto o większym indeksie). Rozwiązanie: oblicz najkrótsze ścieżki między wszystkimi parami za pomocą algorytmu Floyd-Warshall, a następnie dla każdego miasta policz, do ilu innych miast można dotrzeć w ramach podanego progu. Zwróć miasto z najmniejszą liczbą takich miast (w przypadku remisu — to o największym indeksie).
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Ścieżka w ważonym DAG-u
Dla skierowanego grafu acyklicznego (DAG) najkrótsze (lub najdłuższe) ścieżki można znaleźć za pomocą sortowania topologicznego i relaksacji w czasie O(V+E) — szybciej niż algorytmem Dijkstry. Należy przetwarzać węzły w kolejności topologicznej, a podczas przetwarzania węzła u wykonać relaksację wszystkich wychodzących krawędzi. W przypadku najdłuższych ścieżek (przydatnych w planowaniu projektów i wyznaczaniu ścieżki krytycznej) należy zanegować wagi albo zamienić min na 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 distNajkrótsza ścieżka w macierzy z przeszkodami
Popularny wariant zadania rekrutacyjnego polega na znalezieniu najkrótszej ścieżki w dwuwymiarowej siatce od lewego górnego do prawego dolnego rogu, gdy niektóre komórki mogą być zablokowane. Jest to problem BFS w grafie nieważonym (każdy krok kosztuje 1). Należy użyć BFS z poruszaniem się w 4 kierunkach i oznaczać komórki jako odwiedzone w momencie dodawania ich do kolejki, a nie podczas usuwania z kolejki, aby uniknąć ponownych odwiedzin. Jeśli przez przeszkody można przechodzić za określony koszt, należy użyć algorytmu Dijkstry na dwuwymiarowej siatce traktowanej jako graf ważony.
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 z wieloma źródłami
Gdy istnieje wiele punktów początkowych (na przykład wiele „bram” w siatce lub wiele początków na mapie), należy uruchomić BFS z wieloma źródłami: jednocześnie dodać wszystkie źródła do kolejki z odległością 0. W jednym przebiegu BFS oblicza to najkrótszą odległość od najbliższego źródła do każdej komórki. Technika ta pozwala uniknąć uruchamiania BFS osobno dla każdego źródła i ma łączną złożoność O(V+E).
Podsumowanie wyboru algorytmu
Zwięzłe drzewo decyzyjne: jedno źródło, nieujemne wagi → Dijkstra O((V+E) log V). Jedno źródło, ujemne wagi → Bellman-Ford O(VE). Wszystkie pary, małe V → Floyd-Warshall O(V³). DAG, dowolne wagi → sortowanie topologiczne + relaksacja O(V+E). Graf nieważony → BFS O(V+E). Ścieżki w siatce → BFS (graf nieważony) lub Dijkstra z kopcem (graf ważony). Proszę zapamiętać tę tabelę — pozwala ona odpowiadać na pytania uzupełniające podczas każdej rozmowy kwalifikacyjnej dotyczącej najkrótszych ścieżek.
Znajdowanie ścieżki w zadaniach rekrutacyjnych
W wielu zadaniach rekrutacyjnych należy zwrócić rzeczywistą ścieżkę, a nie tylko jej koszt. Zawsze warto doprecyzować: czy potrzebna jest ścieżka, czy tylko odległość? Jeśli potrzebna jest ścieżka, należy od początku utworzyć słownik prev. Typowe błędy to pominięcie inicjalizacji prev[source] = None jako warunku końcowego oraz pomylenie kolejności odtwarzania (należy prześledzić ścieżkę od celu do źródła, a następnie ją odwrócić). Przed zastosowaniem tej techniki do większych problemów warto przećwiczyć odtwarzanie ścieżek na przykładach z 3–4 węzłami.
Szybkie sprawdzenie
Proszę sprawdzić swoją znajomość zagadnień dotyczących struktur danych i algorytmów — przygotowania do rozmów kwalifikacyjnych z programowania — omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo: problem Network Delay Time rozwiązuje się za pomocą max(dist.values()) po uruchomieniu algorytmu Dijkstry, odtwarzanie ścieżki korzysta z tablicy prev aktualizowanej za każdym razem, gdy dist[v] ulegnie poprawie, a także że dwukierunkowy BFS może zmniejszyć przestrzeń przeszukiwania o połowę w przypadku nieważonych najkrótszych ścieżek między pojedynczą parą węzłów. Następnie przejdziemy do porządkowania grafów i algorytmu Kahna do sortowania topologicznego.
Często zadawane pytania
Czy lekcja „Opóźnienie sieci i odtwarzanie ścieżki” jest bezpłatna?
Tak — pełny tekst „Opóźnienie sieci i odtwarzanie ścieżki” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Opóźnienie sieci i odtwarzanie ścieżki”?
Rozwiązywać problem network-delay-time algorytmem Dijkstry, odtwarzać rzeczywistą najkrótszą ścieżkę za pomocą mapy poprzedników oraz omawiać dwukierunkowe BFS dla dużych grafów Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Opóźnienie sieci i odtwarzanie ścieżki”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Algorytm Dijkstry z kolejką priorytetową
- Bellman-Ford i cykle ujemne
- Floyd-Warshall: najkrótsze ścieżki między wszystkimi parami wierzchołków
- Opóźnienie sieci i odtwarzanie ścieżki