DSA Interview Prep · レッスン

優先度付きキューを使うDijkstraのアルゴリズム

Q: 「優先度付きキューを使うDijkstraのアルゴリズム」レッスンは無料ですか？

はい。「優先度付きキューを使うDijkstraのアルゴリズム」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。

Q: DSA Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

Q: 「優先度付きキューを使うDijkstraのアルゴリズム」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

Q: このDSA Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

heapqを使ってDijkstraを実装し、重み付きグラフで緩和の手順を追跡して、cheapest-flights-within-k-stopsを解きます。

「優先度付きキューを使うDijkstraのアルゴリズム」はCoddyKit上の無料DSA Interview Prepレッスンです。これはレッスン1/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。

重み付きグラフの最短経路

ダイクストラ法は、辺の重みが非負の重み付きグラフにおいて、単一の始点ノードから他のすべてのノードまでの最短経路を求めます。現在わかっている最短距離の順にノードを貪欲に処理し、常に未訪問の中で最も近いノードを展開します。中心となるデータ構造は最小ヒープ（優先度付きキュー）で、距離が最小のノードを効率よく取り出せます。

アルゴリズム手順の概要

ダイクストラ法の手順は次のとおりです。(1) dist[source] = 0、dist[all others] = inf と初期化します。(2) (0, source) を最小ヒープに追加します。(3) 距離が最小のノード u を取り出します。すでに、より小さい距離で訪問済みならスキップします。(4) u の各隣接ノード v について、dist[u] + weight(u,v) < dist[v] なら、dist[v] を更新し、(dist[v], v) をヒープに追加します。(5) ヒープが空になるまで繰り返します。

heapqを使ったPython実装

Pythonの heapq は最小ヒープを実装しています。グラフは隣接リストとして、graph[u] = [(v, weight), ...] のように表します。ヒープには (distance, node) のタプルを格納します。よりよい経路が見つかる前に追加されたエントリは古くなっているため、visited 集合を使ってそのようなヒープエントリをスキップします。

import heapq

def dijkstra(graph, source):
    n = len(graph)
    dist = [float('inf')] * n
    dist[source] = 0
    heap = [(0, source)]  # (distance, node)
    visited = set()
    
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(heap, (dist[v], v))
    
    return dist

具体例

5つのノードと次の辺を持つグラフを考えます。0→1 (4)、0→2 (1)、2→1 (2)、1→3 (1)、2→3 (5)、3→4 (3) です。ノード0からの最短経路は、1までが 0→2→1 経由でコスト3、2までがコスト1、3までが 0→2→1→3 経由でコスト4、4までが 0→2→1→3→4 経由でコスト7です。ダイクストラ法は、単一の終点への経路だけでなく、これらすべてを1回の処理で求めます。

import heapq

def dijkstra(graph, source):
    dist = [float('inf')] * len(graph)
    dist[source] = 0
    heap = [(0, source)]
    visited = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

graph = [
    [(1,4),(2,1)],  # 0
    [(3,1)],         # 1
    [(1,2),(3,5)],   # 2
    [(4,3)],         # 3
    []               # 4
]
print(dijkstra(graph, 0))  # [0, 3, 1, 4, 7]

負の重みで Dijkstra が機能しない理由

Dijkstra の正しさは、ノードが最小ヒープから取り出された時点で、その距離が確定しているという事実に依存しています。これは辺の重みが非負の場合にのみ成り立ちます。重みが -5 の負の辺 u→v があると、v を訪問した後で、u を経由するさらに短い経路が見つかる可能性があります。しかし、v にはすでに訪問済みの印が付いています。1本の負の辺だけで、それ以降の距離計算がすべて無効になる可能性があります。

K回以内の乗り継ぎで最安のフライト（LeetCode 787）

この問題には、乗り継ぎが最大で k 回という制約があります。標準的な Dijkstra は、ステップ数をそのまま扱うことができません。解決策は、状態を (cost, node, stops_remaining) に拡張することです。この3要素の組に対して Dijkstra を使うか、k+1 回の緩和パスを行う Bellman-Ford を使います。変更した Dijkstra は stops_remaining が 0 に達した時点で停止し、それ以上のホップを防ぎます。

import heapq
from collections import defaultdict

def findCheapestPrice(n, flights, src, dst, k):
    graph = defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))
    
    heap = [(0, src, k + 1)]  # (cost, node, hops_left)
    visited = {}  # node -> min hops_left seen at this cost level
    
    while heap:
        cost, node, hops = heapq.heappop(heap)
        if node == dst:
            return cost
        if hops == 0:
            continue
        if visited.get(node, 0) >= hops:
            continue
        visited[node] = hops
        for nxt, w in graph[node]:
            heapq.heappush(heap, (cost + w, nxt, hops - 1))
    return -1

print(findCheapestPrice(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1))  # 200

計算量の解析

二分ヒープを使う場合、Dijkstra の時間計算量は O((V + E) log V) です。各頂点は1回ずつ取り出され（V回の取り出し）、各辺によって追加操作が発生する可能性があり（E回の追加）、各ヒープ操作のコストは O(log V) です。フィボナッチヒープを使うと計算量は O(E + V log V) に改善しますが、Python の heapq は二分ヒープです。疎グラフ（E ≈ V）では二分ヒープ版は O(V log V) になり、密グラフ（E ≈ V²）では O(V² log V) になります。

最短経路の復元

距離だけでなく実際の経路も復元するには、prev 配列を保持します。dist[v] を更新するときに、prev[v] = u を設定します。アルゴリズムの完了後、始点から終点までの経路を逆向きにたどって復元します。dst から始め、source に到達するまで prev のポインタをたどり、最後に結果を反転します。

import heapq

def dijkstra_path(graph, source, target):
    n = len(graph)
    dist = [float('inf')] * n
    prev = [-1] * n
    dist[source] = 0
    heap = [(0, source)]
    visited = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited: continue
        visited.add(u)
        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, node = [], target
    while node != -1:
        path.append(node)
        node = prev[node]
    return dist[target], path[::-1]

疎グラフでの Dict の使用

ノードが文字列または連続していない整数の場合は、隣接リストに defaultdict(list) を使い、距離には通常の dict を使います。これは、ノードに 1 から n のラベルが付いている Network Delay Time のような LeetCode の問題でよく使われます。dist = {node: inf for node in all_nodes} を使い、アルゴリズムの後に到達不能なノードがないか確認することを忘れないでください。

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))  # 2

重みなしグラフにおける BFS との比較

重みなしグラフでは、BFS は O(V + E) で最短経路を求められるため、Dijkstra の O((V+E) log V) より高速です。Dijkstra は、通常の FIFO キューの代わりに優先度付きキューを使うことで、BFS を重み付きグラフに一般化したものです。すべての辺の重みが等しい場合、Dijkstra は BFS に帰着します。重みなしグラフには BFS、非負の重みには Dijkstra、負の重みには Bellman-Ford を選んでください。

Decrease-Key 最適化を使う Dijkstra

教科書的な Dijkstra は、decrease-key 操作を持つ優先度付きキューを使います。ノードの距離が改善されたとき、その優先度をキュー内で直接更新します。これには O(E + V log V) を実現するフィボナッチヒープが必要ですが、実装は難しいです。面接で使われる 遅延削除 方式では、代わりに新しい要素を追加し、取り出す際に古い要素をスキップします。実装が簡単で、定数倍のオーバーヘッドしかありません。Python では、heapq を使った遅延削除が面接での標準的な実装です。

理解度チェック

このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。

レッスンのまとめ

このレッスンでは、Dijkstra は最小ヒープを使い、現在の最短距離が小さい順にノードを貪欲に処理すること、O((V+E) log V) の時間で動作し、負の重みを持つ辺では機能しないこと、そして取り出し時に訪問済み集合を確認することで、ヒープ内の古い要素を処理しないことを学びました。次は、V-1 回の緩和パスによって負の重みを扱う Bellman-Ford を取り上げます。

よくある質問