ダイクストラ法の対象試験と出題頻度
ダイクストラ法は「最短経路を求めるアルゴリズム」と説明されがちですが、何をどう最短にするのかが掴みにくい単元です。グラフを見せられた瞬間に手が止まる、という受験生が少なくありません。
頻出度そのものはCランク。ただし午前での単独出題が少ない一方で、応用情報の午後では大問1つを丸ごと占めた実績があります。知らなければ捨て問、手順を知っていれば配点20点級の得点源という、きわめて非対称な用語だと考えてください。
出題情報を確認する
応用情報技術者試験(AP) 基本情報技術者試験(FE)
★★☆☆☆
頻出度C(午前は少数/午後で大問化)
ダイクストラ法の定義
「最短」という言葉だけが独り歩きして、経路の数え上げやクリティカルパスと混ざってしまう。ここが最初のつまずきどころです。
提唱者はオランダの計算機科学者エドガー・ダイクストラ。1959年に発表された、グラフ理論の古典にあたる手法になります。
ダイクストラ法とは、
「重みが負でないグラフで、始点から各ノードへの最短距離を短い順に確定する手法」
です。
乗り換え案内アプリを思い浮かべてみてください。
駅がノード、路線がエッジ、所要時間が重みにあたります。「今わかっている中でいちばん早く着ける駅」から順に印を付けていく作業。人間が路線図の上で無意識にやっている手順が、そのままアルゴリズムになったものだと捉えると腹に落ちます。
📊 ダイクストラ法の基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Dijkstra’s Algorithm(Shortest Path Search) |
| 解く問題 | 単一始点最短経路問題(1つの始点から全ノードへの最短距離) |
| 適用条件 | 重み付きグラフ/単一始点/重みが非負(この3条件セットで暗記) |
| 使う配列 | dist(暫定距離)/done(確定フラグ)/viaNode(直前ノード) |
| 計算量 | O(N²)(優先度付きキュー使用で高速化可能) |
| 実務での例 | カーナビ・経路検索API、OSPFのルーティング計算、配送計画 |
ダイクストラ法の解説|3ステップの反復で最短距離が決まる
順次・選択・繰返しの3構造で書ける処理という点は、他のアルゴリズムと変わりません。押さえるべきは、何を繰り返しているかという1点だけ。
グラフ・ノード・エッジ・重み ─ 3つの言葉だけ押さえれば読める
ノードは地点、エッジはノードを結ぶ線、重みはエッジ1本あたりの距離や所要時間を指します。試験の図はこの3語に置き換えれば必ず読めます。
次の図が、この記事で一貫して使うサンプルグラフです。丸がノード、線がエッジ、線に添えた数字が重みにあたります。
📊 サンプルグラフ(始点V1・重みは非負)
後半のトレース表は、このグラフを始点V1からたどった記録
逆に重みが付いていない図なら、幅優先探索で足りるため、ダイクストラ法の出番はありません。
最短距離が「確定する」とはどういうことか
dist配列には各ノードへの暫定距離を入れ、始点だけ0、残りは十分大きい値で初期化します。より短い道が見つかるたびに、この値は上書きされていく仕組み。
ここで重要なのが、未確定ノードのうち暫定距離が最小のものは、他のどの経路を回ってもこれ以上短くならないという性質。
だからその時点で最短距離として確定でき、done配列に印を付けられます。
3ステップの反復で最短経路が求まる仕組み
擬似言語で何行に膨らんでいても、やっていることは次の3ステップの繰り返しに還元できます。
ダイクストラ法の3ステップ反復
未確定ノードのうち暫定距離が最小のものを探す(dist・doneを参照)
そのノードの最短距離を確定させる(doneに印を書く)
隣接する未確定ノードの暫定距離を書き換える(dist・viaNodeを更新)
この分岐が while の継続条件にあたる
午後問題の擬似言語は、すべてこの3ステップのどこかを穴埋めしている
なぜ負の重みには使えないのか
負の重みが混ざると、いったん確定させた後にもっと短い経路が現れる可能性が生まれます。
ダイクストラ法は確定した距離を後から覆さない構造なので、この状況を処理できません。負の重みを扱いたい場合はベルマン・フォード法。試験ではこの一点が判定軸になると覚えておいてください。
実務では、経路検索APIの裏側で動いているため自分で実装する機会はまれです。ただしネットワーク運用でOSPFのコスト設計を触ると事情が変わります。
「コストを下げた回線に経路が寄る」挙動の理由がまさにこの手法であり、理屈を知っているかどうかで設計変更の予測精度が変わりました。
📊 最短経路系の手法比較
| 手法名 | 目的 | 重みの扱い | 計算量 |
|---|---|---|---|
| ダイクストラ法 | 単一始点の最短距離 | 非負のみ | O(N²) |
| 幅優先探索 | 最少ホップ数の経路 | 重みなし(すべて1) | O(N+E) |
| ベルマン・フォード法 | 単一始点の最短距離 | 負の重みも可 | O(N×E) |
| 線形計画法 | 制約下での最適化全般 | 係数として扱う | 解法により異なる |
📝 ポイント整理
・適用条件は「重み付き」「単一始点」「非負」の3点セット
・反復は「最小を選ぶ→確定する→隣接を更新する」の3ステップだけ
・確定を覆せない構造のため、負の重みには対応不可
試験ではこう出る!ダイクストラ法の出題パターン
出題パターン分析
出方は午前と午後で大きく異なります。まずは自分の受験区分に対応する型を見極めてください。
📝 IPA試験での出題パターン
パターン1:午前・グラフ計算型
図を見て複数ノードへの最短所要時間を手計算し、短い順に並べ替える。ノード数6程度のため、トレース表を書けば確実に取れる。
パターン2:午後・擬似言語穴埋め型
3つの作業配列の操作を穴埋めさせる。距離だけでなく経路そのものを復元させる設問、入れ子構造から計算量を導かせる設問が続く。
午後は表の空欄・プログラムの空欄・経路復元・計算量の4点セットで問われるのが定型。3配列の役割を先に押さえれば、プログラムを全部読まずに解けます。
3つの作業配列の役割を確認する
| 配列名 | 役割 | 初期値 | 書き換わるステップ |
|---|---|---|---|
| dist | 各ノードへの暫定距離 | 十分大きい定数(始点のみ0) | STEP3(参照はSTEP1) |
| done | 最短距離が確定したかの印 | 全ノード未確定 | STEP2 |
| viaNode | 直前に経由したノード番号(経路復元用) | 未設定 | STEP3 |
while ( 未確定のノードが残る )
minDist ← 十分大きい値
for ( k を 1 から N まで ) ・・・最小値探索:最大N回
if ( done[k] が false かつ dist[k] が minDist より小さい )
minDist ← dist[k] / curNode ← k
endif
endfor
done[curNode] ← true
for ( k を 1 から N まで ) ・・・隣接ノード更新:最大N回
if ( dist[curNode] + edge[curNode, k] が dist[k] より小さい )
dist[k] ← dist[curNode] + edge[curNode, k]
viaNode[k] ← curNode
endif
endfor
endwhile
外側のwhileが最大N回、その中のforが最大N回。掛け算でO(N²)が導かれる構造を、この入れ子の見た目とセットで覚えてください。
記法そのものの意味はオーダー記法(計算量)で確認を。
ひっかけポイントと対策
誤答の多くは、別テーマの「最短」との混同から生まれます。次の4行を照合できれば防げます。
⚠️ ひっかけ早見表
| 誤答の値・選択肢 | その正体 |
|---|---|
| 格子状の道の経路が何通りか | 組合せの最短経路数。重みが登場しない別テーマ |
| 全体の完了までの最も長い経路 | クリティカルパス。最長を求めるもので方向が逆 |
| 更新前の暫定距離(例:16) | 確定した時点の値(例:15)が解答 |
| ベルマン・フォード法/幅優先探索 | 負の重み対応・重みなしの手法。条件で切る |
📝 試験区分別の対策方針
・AP:午後の選択候補。トレース表を1回自力で埋め切る訓練を優先
・FE:科目Bで3配列の操作を追えるかが勝負。役割から入る
・IP/SG:出題対象外。用語として知っていれば十分
過去の出題実績を見る
AP 令和6年春 午後問3(プログラミング):カーナビを題材に最短経路を求めるアルゴリズムを扱い、トレース表の空欄、擬似言語の空欄、経路復元、計算量(N²)を問う記述式
AP 平成26年秋 午前問5:頂点V1からV4・V5・V6への最短所要時間を求め、短い順に並べる(正解イ)
FE 平成29年春 午後問8:副プログラム ShortestPath。出発地から目的地への最短経路と距離を求める実質的なダイクストラ法の問題
トレース表で解く!最短経路の求め方3ステップ
午後問題で最初にやるべきは、図と表をノートに写して自分で1回埋め直すこと。
筆者はプログラムの空欄から攻めて時間を溶かした経験があります。表を埋めた時点で「何を更新しているのか」が体に入り、擬似言語の空欄はほぼ自明になりました。
先に示したサンプルグラフを、始点V1からたどった記録が次の表です。
太字は反復で書き換わった値、確定値には色を付けてあります。
📊 ダイクストラ法のトレース表(始点V1)
| 反復 | 更新起点 | V1 | V2 | V3 | V4 | V5 | 確定済み |
|---|---|---|---|---|---|---|---|
| 1回目 | V1 | 0 | 4 | 9 | ∞ | ∞ | V1 |
| 2回目 | V2 | 0 | 4 | 7 | 16 | ∞ | V1, V2 |
| 3回目 | V3 | 0 | 4 | 7 | 16 | 13 | V1, V2, V3 |
| 4回目 | V5 | 0 | 4 | 7 | ( ) | 13 | V1, V2, V3, V5 |
| 5回目 | V4 | 0 | 4 | 7 | 15 | 13 | 全ノード確定 |
4回目の空欄に入る値を、紙の上で出してみてください。
演習の答えと考え方
答えは15。4回目で確定したV5(13)を起点に、V5-V4の重み2を足すと15。それまでの暫定距離16より小さいため、distが16から15へ書き換わります。ここで16を選ぶと更新前の値を答えることになり、失点に直結。「更新起点ノードの確定距離+エッジの重み」で必ず検算してください。
【確認テスト】ダイクストラ法の理解度チェック
Q. ダイクストラ法の説明として、最も適切なものはどれか。
- A. 格子状に配置された道路上で、ある地点から別の地点に至る経路が何通りあるかを数え上げる手法。
- B. 重みが負でないグラフにおいて、ある1つの始点から各ノードまでの最短距離を、確定した距離が短いノードから順に求めていく手法。
- C. 作業の前後関係を矢印で表し、プロジェクト全体の完了までに最も時間がかかる経路を求める手法。
正解と解説を見る
正解:B
解説:
Bは「重みが負でない(非負)」「1つの始点(単一始点)」「短い順に確定」という3要素をすべて含んでいます。この3条件が揃っているかどうかが選択肢を切る基準になります。
Aが不正解の理由:組合せで解く「最短経路の数え上げ」問題。距離・所要時間・コストといった重みが登場しないため、別テーマと判断できます。
Cが不正解の理由:アローダイアグラムのクリティカルパス。求めるのは最長経路であり、最短を求めるダイクストラ法とは方向が逆になります。
ダイクストラ法の関連用語ネットワーク
この手法は、データ構造の知識とネットワーク分野の両方につながる結節点にあります。
📊 関連用語マップ
| カテゴリ | 関連用語 |
|---|---|
| 前提知識 | 木構造・二分木(ノードとエッジの基礎) |
| 関連用語 | RIP(ホップ数のみで経路選択/重み付けの有無が分岐点)、アローダイアグラム(同じ「経路」でも最長を求める別物) |
| 発展 | ヒープソート(最小値探索を優先度付きキューに置き換えると高速化できる) |
📝 この記事のまとめ
・「重み付きグラフ・単一始点・非負」の3条件をセットで覚える
・試験は3条件のどれかを外した選択肢を必ず混ぜてくる
・午後対策はトレース表を1回埋め切ることから始める
・計算量O(N²)は「外側N回×内側N回」の入れ子で導出する