Network Delay Time
ネットワークには、1 から n までのラベルが付いた n 個のノードがあります。リンク times[i] = [u, v, w] は、ノード u からノード v へ、方向はその向きのみで、w 単位の時間をかけて信号を伝えます。
時刻 0 にノード k から信号が発信され、通過可能なすべてのリンクに沿って伝わります。最後のノードが信号を受信する時刻を返してください。受信しないノードがある場合は -1 を返してください。
関数
- timesinteger-2d-array
- 有向リンクをそれぞれ [u, v, w] として
- ninteger
- ノードの数
- kinteger
- 信号を送るノード
- 戻り値integer
- 最後のノードが信号を受信する時刻、または -1
制約
2 ≤ n ≤ 30001 ≤ times.length ≤ 4000times[i].length = 31 ≤ u, v ≤ nかつu ≠ v0 ≤ w ≤ 100- 同じ
uとvの両方を共有するリンクはありません。 1 ≤ k ≤ n
例
- 入力
- times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
- 出力
- 4
- 説明
- 直接のリンクでは時刻 4 にノード 2 に到達しますが、ノード 3 を経由する経路では 1 + 2 = 3 に到達します。ノード 4 が信号を受け取るのは最後で、3 + 1 = 4 の時点です。
- 入力
- times = [[1, 2, 3], [3, 1, 2]]n = 3k = 1
- 出力
- -1
- 説明
- ノード 2 は時刻 3 に信号を受信しますが、ノード 3 に接続しているリンクは 3 から 1 へのものだけです。ノード 3 は信号を受信しないため、答えは -1 です。
- 入力
- times = [[2, 1, 5], [2, 3, 0], [3, 1, 2]]n = 3k = 2
- 出力
- 2
- 説明
- ノード 3 へのリンクは 0 かかるため、ノード 3 は時刻 0 に信号を受け取ります。次にノード 1 は 0 + 2 = 2 の時刻に信号を受け取ります。これは、直接リンクで受け取る時刻 5 よりも早いです。
発展問題
信号が m 個のリンクを越えた後に弱まるとします。その制限のもとで、最後のノードが信号を受信する時刻はどうやって求めますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ノードは、
kからそのノードまでの最速経路の長さに応じた時間で信号を受信します。したがって、答えはそれらの最速時間のうち最大のものです。ただし、経路がまったくないノードがある場合は -1 です。リンクに負の時間はかかりません。したがって、まだ時間が確定していないノードの中で暫定時間が最小のノードが、それ以上速く到達できることはありません。そのノードへの他のすべての経路は、同じくまだ時間が確定していない別のノードを経由し、そこにはそれより早く到達できないためです。到着順にノードを確定させます。
(time, node)ペアの最小ヒープを保持します。最小の要素を取り出し、そのノードにすでにより小さい時刻が設定されている場合はスキップし、時刻が短縮される隣接ノードをすべて追加します。ヒープが空になったら、最大の時刻を取得します。
解説
各ノードが信号を受信するのは、kからそのノードまでの最速経路の長さの時間です。つまり、単一始点最短経路を求めた後に最大値を取ります。ただし、経路のないノードがある場合は -1 です。リンクの所要時間は負になることがないため、Dijkstra のアルゴリズムでは各ノードが一度だけ確定します。以下では、Eはtimes.lengthです。
より速い経路を見つけるたびに再訪する深さ優先探索
正しいが、最大のテストでは終わらない
考え方
kから深さ優先で探索し、ここまでの時間を引き継ぎながら、各ノードへの最速到達時間を記録します。記録された時間より早く到達できない経路はそこで停止し、より早く到達できる経路は記録を更新して探索を続けます。最速経路はどこかの時点で記録を更新するため、最終的に各記録は真の最速時間になります。
ノードは何度も記録を更新することがあります。18個のゲートを一列に並べ、隣り合う各ペアを、コスト0のリンクと、65,536、32,768、以下1まで半減していく迂回路でつなぎます。迂回路を先に試すと、探索は最後のゲートに131,072通りの異なる時間で到達し、そのたびに後ろにあるすべてをたどります。処理量はnに対して指数関数的に増加します。
アルゴリズム
- すべての最良時刻を無限大に設定し、スタックに
(k, 0)をプッシュします。 (node, t)をポップします。t < best[node]でない場合はスキップし、そうでなければbest[node] = tを設定します。nodeからの各リンクについて、到着時刻がbest[next]より早い場合は(next, t + w)をプッシュします。- スタックが空になったら、最良時刻のいずれかが無限大の場合は -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 worstBellman-Ford：各リンクを最大 n-1 回緩和する
考え方
各ノードの暫定時間 dist を保持し、k の値は 0 とします。リンク u → v を緩和すると、dist[u] + w のほうが小さい場合、dist[v] をその値に下げます。Bellman-Ford は各パスですべてのリンクを緩和します。
あるノードへの最速経路を考えてみましょう。たとえば k → a → b → v です。最初のパスで dist[a] が確定し、2回目で dist[b]、3回目で dist[v] が確定します。最速経路でノードが繰り返されることはないため、リンク数は最大でも n-1 です。したがって、n-1 回のパスですべてのノードの値が確定します。
各パスの計算量は O(E) です。3,000 ノードの鎖を終端側から逆順に並べると、4,000 本のリンクに対して2,999回のパスが必要になります。緩和の回数は約1,200万回です。
アルゴリズム
dist[k] = 0に設定し、その他すべてのdistを無限大に設定します。- 最大n-1回繰り返します。各リンク
[u, v, w]について、dist[u] + w < dist[v]の場合は、dist[v] = dist[u] + wに設定します。 - 何も変更されなかったパスの後は、早期に終了します。
distのいずれかがまだ無限大なら-1を返し、そうでなければ最大値を返します。
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最小ヒープを使ったダイクストラ法
考え方
まだ確定していないノードのうち、暫定時間が最小のノードは、すでに最短距離が確定しています。そのノードへの別の経路は、少なくとも同じ時間を持つ未確定ノードを経由して、確定済みノードから出なければなりません。その先のリンクは、負の時間がないため、時間を加算するだけです。そこで、そのノードを確定し、リンクを一度だけ緩和して、これを繰り返します。
最小ヒープを使えば、最小の時間を見つけられます。ノードの値が更新されたら、新しいエントリを追加し、古いエントリはそのまま残します。取り出したエントリの時間がdistより大きければ古いエントリなので、スキップします。各リンクが追加するエントリは最大1つなので、ヒープに保持されるエントリは最大 E + 1 個で、全体の計算量はO(E log E)です。
アルゴリズム
dist[k] = 0に設定し、他のすべてのdistを無限大にして、最小ヒープに(0, k)を追加します。- 最小の
(t, node)を取り出します。t > dist[node]の場合は、古い値としてスキップします。 - 時間
wの各リンクnode → nextについて、t + w < dist[next]の場合は、dist[next] = t + wに設定し、(t + w, next)を追加します。 - ヒープが空になったら、
distのいずれかが無限大の場合は-1を返し、そうでなければ最大値を返します。
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にのみ信号を伝えるため、2つ目の例ではノード3は信号を受信しない。 - 通常の幅優先探索を使う。幅優先探索はリンク数が最も少ない経路を見つけるため、1つ目の例ではノード2の時間が3ではなく4になる。
- -1を忘れる。確認せずに最大値を取ると、無限大が返されるか、信号を受信しなかったノードが隠れてしまう。
- 最大のint値を無限大として使う。すると、到達していない
uではdist[u] + wが負の数にラップアラウンドする。到達していないノードをスキップするか、10^9を使う。
よくある質問3
Network Delay Time の時間計算量はどれくらいですか？
ダイクストラ法と二分ヒープを使う場合、リンク数を E とすると計算量は O(E log E) です。E は n² 以下なので、これは O(E log n) と等しくなります。空間計算量は O(n + E) です。ベルマン–フォード法の時間計算量は O(n · E) です。
なぜダイクストラ法には非負の重みが必要なのですか？
Dijkstraは確定したノードを再訪しません。これは、後からより短い経路が見つからない場合に限り安全です。所要時間が2のリンクA → B、所要時間が3のリンクA → C、所要時間が-2のリンクC → Bがある場合、Bまでの所要時間を2として確定しますが、Cを経由する経路では所要時間1で到達します。Bellman-Fordは負の所要時間を扱えます。
ヒープを使わずに Network Delay Time を解けますか？
はい。単純な配列を使うDijkstraでは、未確定のノードすべてを走査して最小の時間を探すため、合計で O(n²) の計算量がかかります。Eがn²に近い密なグラフでは、こちらが有利です。3,000個のノードと4,000本のリンクのような疎なグラフでは、ヒープ版のほうが処理量を大幅に抑えられます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
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
期待される出力
4