Network Delay Timeと経路復元
Dijkstraでnetwork-delay-timeを解き、先行頂点マップを使って実際の最短経路を復元し、大規模グラフにおける双方向BFSについて学びます。
「Network Delay Timeと経路復元」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
Network Delay Time 問題
Network Delay Time (LeetCode 743) は、n 個のノードと、信号の伝達時間を表す重み付き有向辺からなるネットワークについて、ノード k から送信した信号がすべてのノードに到達するまでの最小時間を求める問題です。到達できないノードがある場合は -1 を返します。これはダイクストラ法を直接適用できる問題で、答えは k から各ノードまでの最短経路距離の最大値です。
解法：ダイクストラ法 + 距離の最大値
始点 k からダイクストラ法を実行し、すべてのノード v について dist[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)) # 2prev 配列による経路復元
距離の計算と同時に実際の最短経路を復元するには、各ノードの最適な直前のノードを記録する 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
1つの始点と終点の組だけが必要な大規模な重みなしグラフでは、双方向 BFSが通常の BFS より大幅に高速になる場合があります。始点と終点の両方から同時に BFS を実行し、2つの探索 frontier が出会った時点で停止します。各 frontier がグラフの深さの半分だけを探索すればよいため、実用上の高速化効果は大きく、探索するノード数は 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。非負の重み付きグラフで、単一始点 → ダイクストラ法。負の重みを含む可能性があり、単一始点 → ベルマン–フォード法。全点対 → Floyd-Warshall（V が小さい場合）または V 回のダイクストラ法（疎グラフの場合）。ホップ数に制約がある場合 → パス数を制限したベルマン–フォード法。面接でこの選択理由を声に出して説明できれば、アルゴリズムへの理解の深さを示せます。
到達可能な近隣都市が最も少ない都市を見つける (LeetCode 1334)
重み付きの経路を持つ都市と distanceThreshold が与えられたとき、しきい値以内で到達できる他の都市の数が最も少ない都市を求めます。同数の場合は、都市番号が大きい方を選びます。解法は、Floyd-Warshallで全点対間の最短経路を計算し、その後、各都市についてしきい値以内で到達できる他の都市の数を数えます。個数が最小の都市を返し、同数の場合は最大の都市番号を返します。
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障害物のある行列上の最短経路
面接でよく出る応用問題として、セルが通行不能になる可能性のある2次元グリッドで、左上から右下までの最短経路を求める問題があります。各ステップのコストが1なので、これは重みなし BFS 問題です。4方向に移動する BFS を使い、再訪を防ぐため、セルはキューから取り出したときではなく、キューに追加したときに訪問済みとして記録します。障害物をコスト付きで通過できる場合は、2次元グリッドを重み付きグラフとして扱い、ダイクストラ法を使います。
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]])) # 4マルチソース BFS
複数の開始地点がある場合（たとえば、グリッド上に複数の「ゲート」がある場合や、地図上に複数の起点がある場合）は、マルチソース BFSを実行します。すべての始点を距離 0 として同時にキューへ追加します。これにより、1回の BFS で各セルから最も近い始点までの最短距離を計算できます。各始点から個別に BFS を実行する必要がなく、全体の計算量は O(V+E) です。
アルゴリズム選択のまとめ
簡潔な選択基準は次のとおりです：単一始点で非負の重み → ダイクストラ法 O((V+E) log V)。単一始点で負の重み → ベルマン–フォード法 O(VE)。全点対で V が小さい → Floyd-Warshall O(V³)。DAG で任意の重み → トポロジカルソート + 緩和 O(V+E)。重みなし → BFS O(V+E)。グリッド上の経路 → BFS（重みなし）またはヒープを使うダイクストラ法（重み付き）。この表を暗記してください。どのような最短経路の面接でも、追加質問に答える際に役立ちます。
面接問題での経路探索
面接問題の多くは、コストだけでなく実際の経路を求めます。まず、経路が必要ですか、それとも距離だけでよいですか？と確認してください。経路が必要な場合は、最初に prev 辞書を用意します。よくある間違いは、終端条件として prev[source] = None を初期化し忘れることと、復元の順序を混同することです。目的地から始点へ逆向きにたどり、その後に逆順にします。より大きな問題に取り組む前に、3～4ノードの例で経路復元を練習してください。
理解度チェック
このレッスンの Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、Network Delay Time はダイクストラ法の後に max(dist.values()) で答えを求められること、経路復元では dist[v] が改善されるたびに更新する prev 配列を使うこと、そして双方向 BFS により、単一の始点と終点の組に対する重みなし最短経路の探索空間を半分にできる場合があることを学びました。次は、トポロジカルソートのための Kahn のアルゴリズムを使って、グラフの順序付けを扱います。
よくある質問
「Network Delay Timeと経路復元」レッスンは無料ですか？
はい。「Network Delay Timeと経路復元」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「Network Delay Timeと経路復元」で何を学びますか？
Dijkstraでnetwork-delay-timeを解き、先行頂点マップを使って実際の最短経路を復元し、大規模グラフにおける双方向BFSについて学びます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「Network Delay Timeと経路復元」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 優先度付きキューを使うDijkstraのアルゴリズム
- Bellman-Fordと負閉路
- Floyd-Warshall：全点対最短経路
- Network Delay Timeと経路復元