0Pricing
Competitive Programming Academy · レッスン

ヒープを使う Dijkstra 法

非負辺上の最短経路を貪欲に求めます

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

最短経路問題

あるノードから他のすべてのノードまでの最も低コストな経路を求めたいとします。すべての辺の重みが0以上なら、Dijkstraで解決できます。

貪欲法の考え方

Dijkstraは貪欲法です。既知の距離が最も小さい未訪問ノードを常に展開し、その距離が確定したものとして扱います。

最小ヒープを使う理由

最も近いノードを高速に取り出すには、最小ヒープが必要です。遅い全探索の代わりに、log n 時間で最小の距離を取り出せます。

import heapq

距離を初期化する

すべての距離を無限大に設定し、始点だけを0にします。到達できないノードは、そのまま無限大になります。

dist = [float('inf')] * n
dist[src] = 0

ヒープに始点を入れる

始点を、(距離, ノード) のタプルとして追加します。距離を先に置くことで、ヒープが自動的にコスト順でエントリを並べます。

pq = [(0, src)]

最も近いノードを取り出す

各ループで、最小の (d, u) をpopします。その d は u までの最短距離なので、取り出した時点で u の処理は完了です。

d, u = heapq.heappop(pq)

古いエントリを無視する

ノードが、より大きい古い距離のままヒープに残っていることがあります。d が保存されている距離より大きい場合はスキップします。

if d > dist[u]:
    continue

隣接ノードを緩和する

緩和とは、隣接ノードへの距離を改善できるか試すことです。u を経由した方が安ければ、距離を更新してヒープに追加します。

if d + w < dist[v]:
    dist[v] = d + w
    heapq.heappush(pq, (dist[v], v))

遅延削除のテクニック

Pythonのヒープではキーを更新できないため、重複したエントリを追加し、古いものを無視します。この遅延方式により、コードを短く高速に保てます。

計算時間

二分ヒープを使うと、Dijkstraの計算量はO((V + E) log V)です。辺が数十万本あるグラフにも十分対応できます。

辺の重みに注意する

Dijkstraは負の辺があると機能しません。取り出した距離が確定値とは限らないためです。その場合はBellman-Fordを使います。

確認問題

(d, u) を取り出したところ、d が dist[u] より大きい場合、どうしますか？

まとめ：ヒープを使うDijkstra

距離を初期化し、(dist, node) を追加し、最も近いものを取り出し、古いエントリをスキップして、隣接ノードを緩和します。これが O((V+E) log V) のDijkstraです。🚀

よくある質問

「ヒープを使う Dijkstra 法」レッスンは無料ですか？

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

「ヒープを使う Dijkstra 法」で何を学びますか？

非負辺上の最短経路を貪欲に求めます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

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

「ヒープを使う Dijkstra 法」レッスンにはどのくらい時間がかかりますか？

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

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

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

このコースのすべてのレッスン

  1. ヒープを使う Dijkstra 法
  2. Deque による 0-1 BFS
  3. Bellman-Ford と負辺
  4. Floyd-Warshall 全点対最短経路
← Competitive Programming Academyに戻る