Network Delay Time ja polun rekonstruointi
Ratkaiskaa network-delay-time Dijkstralla, rekonstruoikaa varsinainen lyhin polku edeltäjäkartan avulla ja pohtikaa kaksisuuntaista BFS:ää suurille graafeille.
Network Delay Time ja polun rekonstruointi on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Network Delay Time -ongelma
Network Delay Time (LeetCode 743): verkossa on n solmua ja signaalin kulkuaikoja kuvaavia suunnattuja, painotettuja kaaria. Tehtävänä on löytää vähimmäisaika, jossa solmusta k lähetetty signaali saavuttaa kaikki solmut. Jos jotakin solmua ei voi saavuttaa, palauttakaa -1. Tämä on Dijkstran suora käyttökohde: vastaus on solmun k lyhimmän polun etäisyyksien maksimi kaikkien solmujen joukossa.
Ratkaisu: Dijkstra + etäisyyksien maksimi
Suorittakaa Dijkstra lähdesolmusta k ja laskekaa dist[v] kaikille solmuille v. Vastaus on max(dist.values()). Jos jokin dist[v] on edelleen inf, solmua ei voi saavuttaa — palauttakaa -1. Signaali kulkee kaikkia polkuja pitkin samanaikaisesti, joten ratkaiseva on solmu, jonka saavuttaminen kestää pisimpään.
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)) # 2Polun rekonstruointi `prev`-taulukon avulla
Kun haluatte laskea etäisyyksien lisäksi varsinaisen lyhimmän polun, ylläpitäkää prev-sanakirjaa, joka tallentaa kunkin solmun parhaan edeltäjän. Aina kun päivitätte arvoa dist[v], asettakaa prev[v] = u. Kun Dijkstra on valmis, seuratkaa kohdesolmusta taaksepäin prev-osoittimia pitkin, kunnes saavutte lähdesolmuun, ja kääntäkää polku lopuksi saadaksenne sen etenemissuunnassa.
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]Kaksisuuntainen BFS suurissa painottamattomissa graafeissa
Suurissa painottamattomissa graafeissa, joissa tarvitaan vain yhden lähde–kohdeparin välinen polku, kaksisuuntainen BFS voi olla huomattavasti tavallista BFS:ää nopeampi. Se suorittaa BFS:ää samanaikaisesti lähde- ja kohdesolmusta ja lopettaa, kun haut kohtaavat. Käytännön nopeutus on merkittävä, koska kummankin rintaman tarvitsee tutkia vain puolet graafin syvyydestä — tutkittavien solmujen määrä pienenee muodosta O(b^d) muotoon O(2 × b^(d/2)), missä b on haarakerroin.
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 -1Milloin mikäkin algoritmi kannattaa valita
Päätösopas: painottamaton graafi, yksi pari → BFS tai kaksisuuntainen BFS. Painotettu, ei-negatiivinen, yksi lähde → Dijkstra. Painotettu, mahdollisesti negatiivinen, yksi lähde → Bellman-Ford. Kaikki parit → Floyd-Warshall (pieni V) tai V × Dijkstra (harva graafi). Rajoitettu hyppyjen määrä → muokattu Bellman-Ford rajoitetulla läpikäyntimäärällä. Tämän valintaperusteen perusteleminen ääneen haastattelussa osoittaa algoritmista kypsyyttä.
Etsi kaupunki, josta on saavutettavissa vähiten naapureita (LeetCode 1334)
Kun annettuna on kaupunkeja ja niiden välisiä painotettuja polkuja sekä distanceThreshold, etsikää kaupunki, josta on kynnysarvon puitteissa saavutettavissa vähiten muita kaupunkeja (tasatilanteissa suositaan suurempaa kaupunki-indeksiä). Ratkaisu: laskekaa kaikkien solmuparien lyhimmät polut Floyd-Warshallilla ja laskekaa sitten kunkin kaupungin kohdalla, kuinka monta muuta kaupunkia voidaan saavuttaa kynnysarvon puitteissa. Palauttakaa kaupunki, jolla on pienin määrä (tasatilanteessa suurin indeksi).
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)) # 3Polku painotetussa DAG-graafissa
Suunnatussa syklittömässä graafissa (DAG) lyhimmät tai pisimmät polut voidaan löytää topologisella järjestämisellä ja relaksoinnilla ajassa O(V+E) — nopeammin kuin Dijkstralla. Käsitelkää solmut topologisessa järjestyksessä ja relaksoikaa solmua u käsitellessänne kaikki sen lähtevät kaaret. Pisimpiä polkuja varten (niitä tarvitaan esimerkiksi projektien aikataulutuksessa ja kriittisen polun laskennassa) voitte kääntää painot vastaluvuiksi tai muuttaa min-operaation max-operaatioksi.
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 distLyhin polku esteitä sisältävässä matriisissa
Yleinen haastattelutehtävä on etsiä lyhin polku kaksiulotteisessa ruudukossa vasemmasta yläkulmasta oikeaan alakulmaan, kun osa soluista voi olla estettyjä. Tämä on painottamaton BFS-ongelma, koska jokainen askel maksaa 1. Käyttäkää neljään suuntaan liikkuvaa BFS:ää ja merkitkää solut vierailluiksi, kun lisäätte ne jonoon (ei vasta kun poistatte ne jonosta), jotta niitä ei tutkita uudelleen. Jos esteiden läpi voi kulkea kustannusta vastaan, käyttäkää kaksiulotteiseen ruudukkoon sovellettua Dijkstraa ja käsitelkää ruudukkoa painotettuna graafina.
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]])) # 4Monilähteinen BFS
Kun lähtöpisteitä on useita (esimerkiksi useita ”portteja” ruudukossa tai useita lähtöpisteitä kartalla), suorittakaa monilähteinen BFS: lisätkää kaikki lähteet jonoon samanaikaisesti etäisyydellä 0. Näin laskette lyhimmän etäisyyden lähimmästä lähteestä jokaiseen soluun yhdellä BFS-läpikäynnillä. Menetelmä välttää BFS:n suorittamisen erikseen jokaisesta lähteestä, ja sen kokonaisaikavaativuus on O(V+E).
Algoritmin valinnan yhteenveto
Tiivis päätöspuu: yksi lähde, ei-negatiiviset painot → Dijkstra O((V+E) log V). Yksi lähde, negatiiviset painot → Bellman-Ford O(VE). Kaikki parit, pieni V → Floyd-Warshall O(V³). DAG, mitkä tahansa painot → topologinen järjestäminen + relaksointi O(V+E). Painottamaton graafi → BFS O(V+E). Ruudukon polut → BFS (painottamaton) tai Dijkstra kekoa käyttäen (painotettu). Opetelkaa tämä taulukko ulkoa — se auttaa vastaamaan minkä tahansa lyhimmän polun haastattelun jatkokysymyksiin.
Polkujen etsiminen haastattelutehtävissä
Monissa haastattelutehtävissä pyydetään kustannuksen sijaan varsinaista polkua. Selvittäkää aina: tarvitaanko polku vai pelkkä etäisyys? Jos polku tarvitaan, alustakaa prev-sanakirja heti alussa. Yleisiä virheitä ovat prev[source] = None -alustuksen unohtaminen päätepisteeksi sekä rekonstruointijärjestyksen sekoittaminen: jäljittäkää polkua kohteesta lähteeseen ja kääntäkää se sitten. Harjoitelkaa polkujen rekonstruointia 3–4 solmun esimerkeillä ennen suurempiin ongelmiin siirtymistä.
Pikatarkistus
Testatkaa tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteiden ymmärtämistä.
Oppitunnin yhteenveto
Tässä oppitunnissa opitte, että Network Delay Time ratkaistaan Dijkstran jälkeen laskemalla max(dist.values()), polku rekonstruoidaan prev-taulukon avulla, jota päivitetään aina, kun dist[v] paranee ja kaksisuuntainen BFS voi puolittaa haun alueen yhden parin painottamattomissa lyhimmissä poluissa. Seuraavaksi siirrymme graafien järjestämiseen Kahn's Algorithmilla topologista järjestämistä varten.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Network Delay Time ja polun rekonstruointi” ilmainen?
Kyllä – oppitunnin ”Network Delay Time ja polun rekonstruointi” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Network Delay Time ja polun rekonstruointi”?
Ratkaiskaa network-delay-time Dijkstralla, rekonstruoikaa varsinainen lyhin polku edeltäjäkartan avulla ja pohtikaa kaksisuuntaista BFS:ää suurille graafeille. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.
Kuinka kauan ”Network Delay Time ja polun rekonstruointi”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Dijkstran algoritmi prioriteettijonolla
- Bellman–Ford ja negatiiviset syklit
- Floyd–Warshall: kaikkien solmuparien lyhimmät polut
- Network Delay Time ja polun rekonstruointi