Network Delay Time
ネットワークにはn個のノードがあり、1からnまでの番号が付いています。そのリンクはリストtimesとして与えられ、times[i] = [u, v, w]は、ノードuから送信された信号がw単位時間後にノードvに到達することを意味します。リンクは一方向にのみ機能します。
時刻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
- 説明
- ノード 3 は時刻 1 に信号を受信します。ノード 2 は直接リンク経由では時刻 4 に受信できますが、ノード 3 を経由する経路では 1 + 2 = 3 に到着し、ノード 4 は 3 + 1 = 4 に受信します。最後に受信するのはノード 4 で、時刻 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 はノード 2 と同時に時刻 0 に信号を受け取ります。次にノード 1 は 0 + 2 = 2 の時刻に信号を受け取ります。これは直接リンクの 5 より早いため、すべてのノードが時刻 2 に信号を受け取ります。
提出時に隠しテスト+16件
発展問題
信号が m 個のリンクを越えた後に弱まるとします。この制限のもとで、最後のノードが信号を受信する時刻をどのように求めますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ノードは、
kからそのノードまでの最速経路の長さの時間で信号を受信します。したがって、答えはそれらの最速時間の最大値です。ただし、経路がまったくないノードがある場合は -1 です。リンクに負の時間がかかることはありません。したがって、まだ時間が確定していないノードの中で暫定時間が最小のノードは、これ以上速く到達できません。そのノードへの他のすべての経路は、これらのノードのいずれかを通り、そのノードにはそれより早く到達できないためです。到着順にノードを確定していきます。
(time, node)のペアの最小ヒープを保持します。最小の要素を取り出し、そのノードにすでにより小さい時刻が設定されている場合はスキップし、時刻が改善するすべての隣接ノードを追加します。ヒープが空になったら、最大の時刻を取得します。
解説
各ノードは、kからの最短経路の長さに応じて信号を受信するため、この課題は有向グラフにおける単一始点最短経路を求め、その後で最大値を求めるものです。答えは最も大きい最短時間です。ただし、経路のないノードがある場合は -1 です。リンク時間は負にならないため、ダイクストラ法では、最小ヒープを使って到着順に各ノードを一度ずつ確定できます。以下では、Eはリンクの数、つまりtimes.lengthです。
より速い経路を見つけるたびに再訪する深さ優先探索
正しいが、最大のテストでは終わらない
考え方
時刻 0 でノード k から探索を始め、これまでの時間を引き継ぎながらすべてのリンクをたどります。各ノードについて、これまでに確認した最速の到着時刻を記録します。探索が記録された時刻以上でノードに到達した場合、そこで停止します。その経路が先のノードにもたらすものは、すでにより速い経路がもたらしているからです。より早く到達した場合は記録が更新され、そのノードの先にあるすべてのものも改善される可能性があるため、そこから探索を続けます。
これは常に正しい方法です。どの記録も改善する経路がなくなったときにのみ探索は停止します。また、各ノードへの最速経路は、いずれかの時点でそのノードの記録を改善するため、最終的にすべての記録は真の最速時間になります。
問題は、ノードが何回改善されるかです。深さ優先探索は、最初に見つけたリンクをたどって奥まで進むため、あるノードに遅い経路で到達したあと、少し速い経路、さらに速い経路で再び到達し、そのたびにノードの先にあるすべての場所を探索することがあります。ゲートが18個、横一列に並んでいる様子を想像してください。各ゲート間では、無料のリンクか、リンクを連ねた迂回路を選べます。迂回路を構成するリンクの所要時間の合計は、65,536、32,768、というように続き、最後は1になります。迂回路を先に試すと、探索は最後のゲートに、前回より速い時刻で131,072通りも到達し、そのたびに背後にある1,700個のノードを探索します。これは約2億2,000万ステップです。大規模なテストのうち2つは、このように作られています。一方は各迂回路を無料のリンクより前に、もう一方は後に並べてあるため、どちらの順序でリンクを試しても、探索はどちらか一方でつまずきます。
アルゴリズム
- 隣接リストを作成します。各ノードについて、そこから出るリンクとその所要時間を記録します。
- すべてのノードの最短時間を無限大に設定し、
(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 worstベルマン–フォード法：すべての辺を最大 n-1 回緩和する
考え方
各ノードの暫定時間 dist を保持します。k は 0、それ以外は無限大です。リンク u → v を時間 w で緩和するとは、dist[u] + w が dist[v] より小さい場合、そのリンクを通れば v により速く到達できるため、dist[v] をその値に下げることです。Bellman-Ford はリンク全体のリストを繰り返し走査し、各パスで各リンクを緩和します。
なぜこれで正しい時間が求まるのでしょうか。あるノードへの最速経路が k → a → b → v だとします。最初のパスでは、dist[k] はすでに 0 なので、k → a が緩和され、その後 dist[a] が確定します。2 回目のパスで dist[b] が確定し、3 回目で dist[v] が確定します。ループの時間は負にならないため、最速経路で同じノードを 2 回訪れる必要はありません。したがって、経路に含まれるリンクは最大でも n-1 本であり、n-1 回のパスですべてのノードの値が確定します。何も変化しないパスがあれば、それ以降のパスで値が変わることはないと分かるため、そこで処理を終了します。
各パスの計算量は O(E) なので、最悪の場合は O(n · E) です。リスト内の順序によって、処理の重さは変わります。長い経路のリンクが終点側から始点側へ向かう順に並んでいる場合、各パスで確定するノードは 1 つずつ増えます。大規模なテストケースの 1 つは、まさにこのケースです。3,000 個のノードがつながるチェーンを逆順に並べ、4,000 本のリンクを 2,999 回走査するため、緩和処理は約 1,200 万回になります。この規模ならまだ時間内に実行できますが、処理量は n と E の積に応じて増えます。Bellman-Ford の強みは別のところにあります。リンクの時間が負の場合でも正しく動作しますが、Dijkstra はそうしたケースで失敗します。
アルゴリズム
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最小ヒープを使ったダイクストラ法
考え方
Bellman-Ford は、まだ時刻が確定していないノードから出るリンクを緩和するため、無駄なパスを繰り返し、そのノードに戻ってくる必要があります。Dijkstra のアルゴリズムは、各ノードの時刻が確定した時点で、そのノードのリンクをちょうど一度だけ緩和します。問題は、いつ時刻が確定したと判断できるかです。
答えは貪欲なルールです。まだ確定していないノードのうち、暫定時刻が最小のノードの時刻は、すでに確定しています。そのノードに至る別の経路は、どこかで確定済みのノードを離れ、少なくとも同じ大きさの時刻を持つ未確定ノードを通らなければなりません。また、その先のリンクは時刻を増やすだけです。負のリンクはないからです。そこで、そのノードを確定し、リンクを緩和してから、同じ手順を繰り返します。最初の例では、ノード 1 の時刻が 0 で確定し、ノード 2 の時刻 4 とノード 3 の時刻 1 が候補になります。ノード 3 の時刻が最小なので、時刻 1 で確定し、ノード 2 の時刻を 3 に下げます。ノード 2 は時刻 3 で確定し、ノード 4 の時刻 4 が候補になります。ノード 4 は最後に確定します。答えは 4 です。
最小ヒープを使うと、暫定時刻の最小値をすばやく見つけられます。ノードの時刻が更新されるたびに (time, node) をプッシュし、古いエントリを探して削除する代わりに、ヒープ内に残しておきます。古いエントリが後で取り出されたとき、その時刻はノードの現在の時刻より大きいため、スキップします。各リンクによってプッシュされるエントリは最大 1 つなので、ヒープ内のエントリ数は E + 1 を超えず、各プッシュまたはポップのコストは O(log E) です。したがって、全体の計算量は O(E log E)、隣接リスト、時刻、ヒープに必要な空間計算量は O(n + E) です。
貪欲なルールが安全に成り立つのは、時刻が非負の場合です。時刻 2 のリンク A → B、時刻 3 のリンク A → C、時刻 -2 のリンク C → B を考えてみましょう。Dijkstra は B の時刻を 2 で確定しますが、C を通る経路では時刻 1 で到達できます。信号が送信される前に到着することはないため、ここでの時刻はすべて 0 以上であり、このルールが成り立ちます。
アルゴリズム
- 各ノードについて、
(next, w)のペアの隣接リストを作成します。 dist[k] = 0に設定し、それ以外のすべてのdistを無限大に設定して、(0, k)を最小ヒープに追加します。- 最小の
(t, node)を取り出します。t > dist[node]の場合、そのエントリは古いため、スキップします。 - それ以外の場合、
tは確定値です。nodeからnextへの時間wの各リンクについて、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つ目の例では、ノード3を経由する時間3の経路ではなく、直接のリンクによる時間4の経路がノード2に返されます。
- ノードをヒープから取り出したときではなく、追加したときに確定済みとしてマークする。ノードに最初に提示される時間が最善とは限りません。ヒープから取り出された最小の値だけが確定値です。
- -1を忘れる。確認せずに最大値を取ると、無限大を返すか、最大の有限時間を報告して、シグナルを受け取らなかったノードを見落とします。
- ノードを0から数える。ノードには1からnまでのラベルが付いているため、配列のサイズは
n+1にし、未使用のスロット0を最大値の計算から除外します。 - 無限大によるオーバーフロー。無限大が最大のint値の場合、未到達の
uについてdist[u] + wを計算すると、負の数にラップアラウンドします。未到達のノードをスキップするか、余裕のある10^9などの値を使います。
よくある質問4
Network Delay Time の時間計算量はどれくらいですか？
Dijkstraのアルゴリズムと二分ヒープを使うと、Eをリンク数として、時間計算量はO(E log E)です。Eは最大でもn²なので、これはO(E log n)と同じです。隣接リスト、時刻、ヒープに必要な空間計算量はO(n + E)です。Bellman-Fordの時間計算量はO(n · E)、空間計算量はO(n)です。
なぜダイクストラ法には非負の重みが必要なのでしょうか？
Dijkstra法は、暫定時間が最小のノードを確定し、そのノードを二度と調べません。これは、後からより短い経路が見つからない場合にのみ安全です。重みがすべて非負であれば、未確定ノードを経由する経路のコストは、そのノードの時間以上になります。負の辺があると、この論拠は成り立ちません。一見コストが高そうなノードを経由する経路でも、結果的により安くなることがあります。重みが負の場合は、Bellman-Fordを使ってください。
Network Delay Time に BFS を使わないのはなぜですか？
BFSは、開始地点からのリンク数が少ない順にノードを訪問します。これは、すべてのリンクに同じ時間がかかる場合にのみ、到着時刻の順序と一致します。ここではリンクごとに所要時間が異なるため、リンク数が多い経路のほうが早く到着することがあります。すべての所要時間が等しければBFSで十分であり、所要時間が0と1のみの場合は、dequeを使った0-1 BFSが機能します。
ヒープを使わずに Network Delay Time を解けますか？
はい。単純な配列を使うダイクストラ法では、未確定のノードをすべて調べて最小時間のノードを探すため、合計で O(n²) の計算量がかかり、ヒープは不要です。E が n² に近い密グラフでは、こちらのほうが適しています。一方、ここでの大規模なテストのようにノードが 3,000 個、リンクが 4,000 個の疎グラフでは、ヒープ版のほうが処理量を大幅に減らせます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
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