問題の要件と範囲
n 個のノード（ラベルは 0 から n - 1）を持つ有向グラフが与えられます。各辺はタプル (from, to, weight) で表されます。source と target が与えられたとき、始点から終点までの最短距離と 1つの最短経路を含むペアを返してください。終点に到達できない場合は (-1, []) を返してください。
このバージョンでは、1 <= n <= 100000、0 <= m <= 300000、すべてのノードラベルが有効であること、および 0 <= weight <= 10^9 を前提とします。多重辺、重み 0 の辺、および自己ループは許可されます。source と target は有効なラベルです。これらが等しい場合は (0, [source]) を返してください。同じ距離の最短経路が 複数存在する場合は、そのうちのいずれかを返せば許容されます。
例えば、辺 (0, 1, 4)、(0, 2, 1)、(2, 1, 2)、(1, 3, 1)、(2, 3, 5)、 (3, 4, 3)、および (2, 4, 12) の場合、0 から 4 への答えは距離 7、経路 [0, 2, 1, 3, 4] となります。
非負の重みという条件は、アルゴリズムの前提条件（コントラクト）の一部です。重み付きグラフであること自体が ダイクストラ法を意味するわけではありません。重みなしグラフなら BFS が適しており、DAG であればトポロジカル動的計画法が使用でき、 負の辺を含む一般的なグラフにはベルマン・フォード法などのアルゴリズムが必要です。
面接官が評価するポイント
最初の評価シグナルは、前提条件に基づいたアルゴリズムの選択です。辺の重みが 非負であり、単一始点の問題であるため、ダイクストラ法が適しています。負の重みについて確認せずに「重み付きグラフだから ダイクストラ法」と答える候補者は、決定的な前提条件を見落としています。
2つ目のシグナルは、データ構造の不変条件です。隣接行列は O(V^2) の空間を必要とするため、 最大 100,000 ノードに対しては不適切です。隣接リストは探索で使用する V + E の情報 のみを保持します。最小ヒープは、発見された距離が最小の未確定ノードを取得します。
3つ目のシグナルは、距離の減少（更新）をどのように表現するかです。Python の heapq は、 任意の要素をその場で更新できません。実用的な解決策は、新しい (distance, node) のペアをプッシュし、 後でその距離が distances[node] と等しくなくなった古いペアをスキップすることです。この遅延削除（lazy deletion）の詳細は 見落とされがちですが、正当性の論理と厳密な計算量の上界の双方に影響します。
面接官は単に動作するコードだけでなく、証明も期待しています。優れた回答では、ノードに対して最初に取り出された 現在のエントリがなぜ確定値となるのか、なぜ非負の重みによってその貪欲なステップが安全になるのか、そしてなぜ 終点が最初に発見された時点ではなく、ヒープから取り出された時点で結果を返せるのかを説明します。経路の 復元、到達不能な入力、重み 0 の辺、多重辺、整数の幅、および敵対的テストケースまで言及することで回答が完成します。
回答前に確認すべき明確化のための質問
- 辺の重みは負になり得ますか？ 基本問題では負にはならないとされています。もし負の辺が許可される場合、
ダイクストラ法の確定の証明および早期終了は成り立ちません。
- グラフは有向グラフですか？ はい。無向グラフの場合は、隣接リストに双方向を追加します。
- 距離のみが必要ですか、それとも経路も必要ですか？ このバージョンでは両方が必要なため、緩和（relaxation）によって
距離が厳密に改善されるたびに先行ノード（predecessor）を記録します。
- 多重辺、重み 0 の辺、または自己ループは存在し得ますか？ はい。緩和処理によって前処理なしで
処理されます。非負の自己ループが自身のノードの距離を改善することはありません。
- 「到達不能」とは何を意味すべきですか？
(-1, [])を返します。長さ 0 の経路と混同しないでください。 - 複数の最短経路が存在する場合、どれか1つでよいですか？ はい。実装では厳密な改善時のみ先行ノードを
更新するため、同等の代替ルートによって経路木が無駄に変化することはありません。
- 距離は最大でどれくらい大きくなりますか？ 単純最短経路は最大で
n - 1本の辺を持つため、指定された
制約下では 10^14 未満になります。Python の整数は無制限ですが、固定幅の言語では 64 ビット整数を使用してください。
30秒の回答フレームワーク
「隣接リストを構築し、これまでに発見された distances[v] から v への最良距離を保持する配列を管理します。 始点を 0 に初期化し、(0, source) を最小ヒープに入れます。最小のエントリを取り出すたびに、 それが古い情報（stale）であればスキップします。そうでなければ、残りのすべての辺の重みが非負であるため、そのノードの距離は確定します。 各出辺を緩和し、厳密な改善があるたびに新しいヒープエントリをプッシュし、経路復元のために先行ノードを記録します。終点の現在の エントリが取り出された時点で探索を終了できます。終点の距離が無限大のままであれば (-1, []) を返し、 そうでなければ先行ノードを逆順にたどって経路を反転します。遅延ヒープエントリを用いた場合、時間計算量は O((V + E) log E)、空間計算量は O(V + E) です。」
ステップバイステップの詳細解説
まず、発見された経路と、最短であることが証明された経路を区別することから始めます。distances[v] は、 無限大か、または既に発見された実際の経路の長さであるため、真の最短距離の上界となります。重み w の辺 u -> v を 緩和することは、u を経由するルートの方が優れているかどうかをテストすることです： distances[u] + w < distances[v]。厳密な改善があれば、距離と previous[v] の両方が更新されます。
ヒープには同一ノードに対する複数のエントリが含まれることがあります。例において、辺 0 -> 1 は最初に 距離 4 を挿入します。ノード 2 が処理された後、ルート 0 -> 2 -> 1 によりノード 1 が距離 3 に改善され、2つ目の エントリが挿入されます。最終的に (4, 1) が取り出されたとき、4 != distances[1] となるため、これは古い情報であり 無視する必要があります。明示的なヒープ要素の削除やノードの訪問済みセットは不要です。
from heapq import heappop, heappush
def shortest_path(
n: int,
edges: list[tuple[int, int, int]],
source: int,
target: int,
) -> tuple[int, list[int]]:
graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]
for node, neighbor, weight in edges:
if weight < 0:
raise ValueError("Dijkstra requires non-negative edge weights")
graph[node].append((neighbor, weight))
distances = [float("inf")] * n
previous = [-1] * n
distances[source] = 0
heap: list[tuple[int, int]] = [(0, source)]
while heap:
distance, node = heappop(heap)
if distance != distances[node]:
continue
if node == target:
break
for neighbor, weight in graph[node]:
candidate = distance + weight
if candidate < distances[neighbor]:
distances[neighbor] = candidate
previous[neighbor] = node
heappush(heap, (candidate, neighbor))
if distances[target] == float("inf"):
return -1, []
path = []
node = target
while node != -1:
path.append(node)
node = previous[node]
path.reverse()
return int(distances[target]), path正当性の議論には2つの部分があります。第1に、distances 内のすべての有限値は、実際に発見された経路の長さであるため、 真の最短経路距離より小さくなることはありません。第2に、u の現在のエントリが取り出されたものの、u へのより短い経路が存在すると仮定します。 その経路上の、まだ確定（settled）していない最初のノードを取り、その先行ノードを x とします。ノード x はそれ以前に確定していたため、 その出辺は緩和済みです。したがって、最初の未確定ノードには、u への仮定上のより短い経路の長さ以下のヒープキーが割り当てられていました。 残りのすべての辺の重みは非負であるため、そのキーは u の取り出されたキーよりも小さく、先にヒープから取り出されていたはずであり、これは矛盾です。 したがって、取り出された現在の距離は確定値となります。
この証明は、安全な早期終了のタイミングも定義しています。終点が、古くない現在の距離でヒープから取り出された後にのみ終了してください。 辺が最初に終点を発見した時点で終了してはなりません。後からより良いルートが見つかる可能性があるためです。 サンプルグラフでは、ノード 4 の直接の発見コストは 13 ですが、最終的なルートのコストは 7 です。
previous[v] = u は、現時点で最良の v への経路の最後の辺を記録します。終点の距離が 確定したら、各先行ノードの割り当ては始点を起点とする実際のルートから来ているため、先行ノードをたどることで必ず始点に到達します。 その連鎖を反転させることで、順方向の経路が得られます。始点と終点が等しい場合、 始点は即座に取り出され、経路復元は [source] を返します。
隣接リストの構築には O(V + E) の空間と O(E) の時間がかかります。緩和が成功するたびにヒープエントリが 1つプッシュされるため、最初の始点エントリに加えて、このようなプッシュは最大で E 回発生します。遅延による重複を含めると、 ヒープには最大 O(E) 個のエントリが含まれる可能性があり、時間計算量は O((V + E) log E)、全体の空間計算量は O(V + E) となります。教科書では、decrease-key 操作をサポートするヒープに対して O((V + E) log V) と記述されたり、 単純な疎グラフに対してそのように簡略化されたりすることがよくあります。遅延実装における log E の上界を明記する方がより正確です。
正常系だけでなく、前提条件の境界もテストしてください。サンプルは (7, [0, 2, 1, 3, 4]) を返す必要があります。 多重辺と重み 0（(0, 1, 10)、(0, 1, 2)、(1, 2, 0)）では、 (2, [0, 1, 2]) を返す必要があります。また、到達不能な終点、始点と終点が同じ場合、自己ループ、同等コストの 代替経路、および重み 0 の辺もテストしてください。負の辺が含まれている場合は、前提条件が破られた状態で暗黙的に結果を出すのではなく、 明示的なエラーを発生させる必要があります。
小規模な差分テストとして、非負の重みを持つグラフを生成し、すべての始点からこの関数を実行して、 その距離をベルマン・フォード法と比較することができます。返された経路については、最初と最後のノードを検証し、 すべての連続するペアが入力の辺であることを検証し、選択された辺の重みの合計を検証します。多重辺がある場合、 テストは各ノードペアに1本の辺しかないと仮定するのではなく、経路のステップを一致する辺の重みと関連付ける必要があります。
高品質な回答例
「まず、すべての辺の重みが非負であること、グラフが有向であること、および任意の最短経路が1つ得られれば 許容されることを確認します。これらの条件により、ダイクストラ法を使用できます。グラフには最大 100,000 個のノードと 300,000 本の辺が存在する可能性があるため、出辺は隣接リストに保存します。隣接行列では大きすぎます。
distances[v] は、始点（0 で初期化）を除き、無限大で初期化します。最小ヒープには発見された (distance, node) のペアを保存します。現在のノードを経由するより短いルートが見つかったら、隣接ノードの 距離と先行ノードを更新し、新しいペアをプッシュします。heapq には任意の decrease-key 操作がないため、 古いペアはヒープ内に残ります。これらは取り出された距離と現在の配列の値を比較することで検出し、一致しないものはスキップします。
重要な証明は確定の不変条件（settling invariant）です。ノード u に対する現在のエントリがヒープの最小値であるとき、 仮定上のより短いルートが存在するとすれば、そこには先行ノードが既に確定している最初の未確定ノードが含まれているはずです。 その先行ノードの緩和によって、同等以下のプレフィックス距離がヒープに追加されていたはずです。 残りの重みが非負であるということは、そのプレフィックスは u よりも先に取り出されていなければならず、これは矛盾です。 したがって、u は確定値です。これが、終点が最初に発見された時ではなく、終点の現在のエントリが取り出された時に 終了できる理由です。
終点の距離が無限大のままであれば、(-1, []) を返します。そうでなければ、終点から始点へと 先行ノードポインタをたどり、それを反転します。緩和が成功するたびに作成される新しいヒープエントリは最大1つのため、 この遅延実装は O((V + E) log E) の時間で動作し、O(V + E) の空間を使用します。固定幅の言語では 64 ビットの距離を使用します。古いエントリ、多重辺や重み 0 の辺、同等コストの経路、始点と終点が同じケース、 到達不能な入力、および負の辺の拒否をテストします。」
よくある間違い
- 負の重みについて確認せずにダイクストラ法を実行する → 貪欲法による確定の証明が破綻する →
非負の重みを明示的な前提条件とし、無効な入力を拒否する。
- 終点が最初に緩和された時点で終了する → 最初に発見されたルートが高コストである可能性がある →
終点の現在のヒープエントリが取り出されたときにのみ終了する。
- 古いヒープエントリを処理してしまう → 古い距離によって出辺が無駄に繰り返し走査される → **
distance != distances[node]の場合に
スキップする。**
- ノードが最初にプッシュされたときに訪問済みとしてマークする → 後から見つかるより短いルートが破棄される → **ノードは
現在の最小エントリがヒープから取り出されたときにのみ確定状態になる。**
- 隣接行列を使用する → 疎グラフの入力で
O(V^2)のメモリを消費する → **O(V + E)の記憶領域を持つ
隣接リストを使用する。**
- 同等距離の際にタイブレークのルールなしで先行ノードを更新する → 重み 0 のサイクルによって経路の選択が
不安定になる → 任意の最短経路で十分な場合は厳密な改善のみを採用する。
- 有限の距離を返すが経路の要件を満たさない → 実装が問題の要件を満たせない →
厳密な改善ごとに先行ノードを記録し、探索後に復元する。
- 断りなくこのヒープ実装を
O(E log V)と呼ぶ → 遅延重複によりヒープサイズが
E に比例する可能性がある → O((V + E) log E) を明記した上で、従来の decrease-key による上界を説明する。
- 32 ビットの距離を使用する → 経路の合計が約 21 億を超える可能性がある → Python の整数または 64 ビット型を使用する。
- 最終距離のみをテストする → 先行ノードの連鎖の不備が見落とされる → **経路の端点、
辺、および合計された重みも検証する。**
フォローアップとその対処法
フォローアップ 1: 距離のみが必要な場合、何が変わりますか？
previous 配列と経路の復元処理を削除します。探索、証明、および漸近的計算量の上界は同じままですが、 補助的なノード記憶領域が O(V) 配列 1 つ分削減されます。終点の現在のエントリが取り出された時点での 早期終了は引き続き安全です。
フォローアップ 2: 全点対間の最短距離が必要な場合はどうしますか？
すべてのノードからダイクストラ法を実行すると、この実装では O(V(V + E) log E) のコストがかかります。 密グラフの場合、ワーシャル・フロイド法は O(V^3) の時間と O(V^2) の空間を使用し、負の閉路がなければ 負の辺も扱えます。ジョンソンのアルゴリズムは、負の閉路のない負の辺を持つ疎グラフに対して、ポテンシャルを用いた重み再設定と反復ダイクストラ法を組み合わせます。実際のグラフの密度とクエリ数に応じて選択してください。
フォローアップ 3: 負の辺が許可されている場合はどうしますか？
一般的な有向グラフにはベルマン・フォード法を使用します。すべての辺を繰り返し緩和し、O(VE) で動作し、 さらに緩和が成功した場合は到達可能な負の閉路を検出できます。 反例 0 -> 1 = 2, 0 -> 2 = 5, 2 -> 1 = -10 はこの問題を示しています。早期終了するダイクストラ法は終点 1 を 2 で確定してしまいますが、ノード 2 を経由する真のルートのコストは -5 です。
フォローアップ 4: グラフが DAG で、一部の辺が負である場合はどうしますか？
DAG をトポロジカルソートし、トポロジカル順に各ノードの出辺を1回ずつ緩和します。すべての先行ノードは 後続ノードの前に処理されるため、負の重みがあっても安全であり、総時間は O(V + E) です。これは、 非巡回というより強い前提条件の下ではベルマン・フォード法やダイクストラ法よりも優れています。
フォローアップ 5: すべての重みが 0 または 1 の場合はどうしますか？
両端キュー（deque）を用いた 0-1 BFS を使用します。重み 0 の緩和は先頭に、重み 1 の緩和は 末尾にプッシュします。deque は広義単調増加の距離順序を保持するため、ヒープなしで O(V + E) の時間で動作します。
フォローアップ 6: 頻繁な辺の更新がある場合、設計はどのように変わりますか？
たまの更新であれば、隣接リストを再構築するか影響を受ける辺を変更してダイクストラ法を再実行します。 単純な解決策が最も検証しやすいです。レイテンシ要件が厳しい頻繁な更新の場合は、動的最短経路手法や、 無効化処理を備えたキャッシュ済み始点木が必要になります。その有用性は更新/クエリ比率とグラフ構造に依存します。「局所的な辺の変更は、その両端の2ノードにしか影響しない」などと主張してはなりません。
フォローアップ 7: 辞書順で最小の最短経路を返すにはどうしますか？
厳密な距離比較だけでは不十分です。同一コストの最初の経路が無条件に保持されてしまうためです。 まず順序の定義（コントラクト）を明確にします。1つのアプローチは、最短距離を計算し、それらの距離と整合する辺のみに候補遷移を制限した上で、終点への到達可能性を維持しながら辞書順で最小の有効な次ノードを選択していく方法です。重み 0 のサイクルには、サイクルを意識した処理が必要です。各ヒープエントリ内で完全な経路タプルを比較する方法は、小さな入力に対しては単純ですが、コピーや比較の大幅なオーバーヘッドが発生する可能性があります。