基本情報のダイクストラ法を更新表と例題で理解する

ダイクストラ法の表を追うときに大切なのは、「次に選ぶ辺」と「次に確定する頂点」を混同しないことです。選ぶのは、始点からの暫定距離が最小の未確定頂点。その頂点までの距離に、隣へ進む辺の重みを足して、今の値より小さければ更新します。

基本情報で最短経路を学ぶ方に向けて、この記事では独自のグラフを使い、距離が書き換わる理由を一行ずつ確認します。最後には辺の重みを変える練習問題と誤答の見分け方を用意しました。距離だけでなく、実際に通る経路も自分で復元できるようになるのが目標です。

基本情報のダイクストラ法で距離を確定する

始点からの合計を比べるアルゴリズム

ダイクストラ法は、辺に重みがあるグラフで、ひとつの始点から各頂点までの最短距離を求める方法です。頂点は地点、辺は地点間の移動、重みは距離や所要時間などを表します。ここでいう距離は図の線の見た目の長さではなく、経路上に書かれた重みの合計です。

例えば、直通する辺の重みが12でも、途中の地点を経由した合計が4＋3＝7なら、最短距離は7になります。通過する辺の本数が少ない経路が最短とは限りません。図で一直線に近く描かれているかどうかにも左右されないので、まず足し算で比較する問題だと捉えると整理できます。

前提は、すべての辺の重みが0以上であることです。0の辺を含むグラフにも使えますが、負の辺を含むグラフでは通常の確定手順の正しさを保証できません。また、有向グラフでは矢印の方向だけに進めます。A→Bの辺があっても、B→Aへ戻れるとは限りません。

IPAの基本情報技術者試験シラバスVer.9.2でも、ダイクストラ法は「グラフのアルゴリズム」の用語例に含まれています。用語の暗記だけで終わらず、どの頂点を確定し、どの配列を書き換えるのかまで説明できるようにしておきましょう。

配列内から値を探す線形探索や二分探索とは、解く対象が異なります。探す値と並び順を使う探索を整理したいときは、基本情報の線形・二分・ハッシュ探索と読み分けると、同じ「探索」という言葉でも目的の違いがつかめます。

ひとつの始点から全頂点への距離が求まっても、すべての頂点どうしの最短距離を求めたことにはなりません。例えばSからTへの結果だけでは、AからBへ行けるかどうかも決まりません。問題に「出発地から各地点へ」とあるのか、「すべての地点の組合せ」とあるのかも読み分けてください。

暫定距離と確定距離を分ける

暫定距離とは、現在までに見つかった経路の中で最も小さい距離です。まだ調べていない経由地を使えば、もっと短くなる可能性があります。一方、確定距離は、それ以上短くならないと判断できた最短距離です。同じ数値の欄でも、未確定か確定済みかで意味が違います。

初期状態では、始点の距離を0、それ以外を∞と置きます。始点から始点まで何も移動しない距離は0です。∞は「本当に無限の長さがある」という測定結果ではなく、「到達する経路がまだ見つかっていない」ことを表す記号です。辺がない地点へ、いきなり0を書き込まないようにしましょう。

管理する情報は、距離・確定済みかどうか・直前の頂点の3種類です。距離の値だけが並んでいると、同じ頂点を何度も確定したり、どこを経由した値なのか見失ったりします。手計算では距離の横に確定印を付け、別の欄に直前の頂点を残すだけでも混乱を減らせます。

記録する情報	内容	初期値の例
距離d[v]	始点から頂点vへの最短距離候補	始点は0、ほかは∞
確定済みfixed[v]	最短距離を確定したか	すべて未確定
直前の頂点prev[v]	現在の候補経路でvの直前にいる頂点	未設定

例えばAの距離が7から5になったとき、変わったのは「Aの最短距離候補」です。その時点で自動的にAが確定するわけではありません。距離の更新は候補を改善する処理、確定は未確定の候補を全体で比較して選ぶ処理と、役割を分けて覚えるのがコツです。

問題によっては、始点の確定と最初の更新を済ませた状態から表が始まります。その場合、始点以外の一部に有限の値が入っていても、初期化が誤っているとは限りません。与えられた表が「初期化直後」なのか「始点の処理後」なのかを読み、処理済みの段階を二重に実行しないことが大切です。

確定してから隣の候補を更新する

繰り返す処理は3つです。まず未確定の頂点の中から暫定距離が最小の頂点uを選び、次にuを確定します。その後、uから直接進める未確定の頂点vについて、uを経由する距離を計算し、今の暫定距離より小さい場合だけ書き換えます。

更新の比較はd[u]＋重み(u→v)とd[v]です。前者が小さければd[v]をその値にし、prev[v]をuにします。前者が大きければ何も変えません。前者と後者が同じ場合も、この記事では距離も直前の頂点も変えないルールにします。

最小の暫定距離を選んだ時点で確定できるのは、非負の重みなら、これから未確定の地点を回っても距離を減らせないからです。仮にuより短い別経路があるなら、その途中にある最初の未確定頂点までの候補もuより小さくなるはずです。それでは「uが未確定の中で最小」という選び方に矛盾します。

この考え方は、甲南大学の最短経路問題の講義資料で説明される、始点から近い地点の到達コストを順に確定する手順に対応します。「近い」は現在位置からではなく、あくまで始点からの合計です。

ここで、ひとつの頂点から枝分かれする候補をすべて更新したあと、再び未確定全体を比較することが重要です。直前に調べた頂点の隣だけを見て次へ進む方法ではありません。紙の表でも、更新を終えるたびに未確定の列を横断して最小値を探しましょう。

独自グラフの距離を更新表で追う

ここからは独自の練習用グラフを使います。始点はS、目的地はTです。頂点はS・A・B・C・D・T・Uの7個で、Uにはどの辺も接続していません。次の表に示す有向辺だけが存在し、逆方向の辺はないものとします。数値の単位は共通のコストです。

出発する頂点	進める頂点と辺の重み
S	Aへ7、Bへ3、Cへ11
B	Aへ2、Cへ6、Dへ8
A	Cへ2、Dへ5
C	Dへ1、Tへ7
D	Tへ2
T・U	出ていく辺なし

表を自分で書く場合は、左からS・A・B・C・D・T・Uの列を用意します。「各頂点を確定し、その頂点からの更新をすべて終えた直後」を1行として記録します。更新前と更新後を混ぜると同じ表でも答えがずれるため、行のタイミングを最初に決めておきます。

処理直後	S	A	B	C	D	T	U
初期化	0	∞	∞	∞	∞	∞	∞
Sを確定・更新	0確	7	3	11	∞	∞	∞
Bを確定・更新	0確	5	3確	9	11	∞	∞
Aを確定・更新	0確	5確	3確	7	10	∞	∞
Cを確定・更新	0確	5確	3確	7確	8	14	∞
Dを確定・更新	0確	5確	3確	7確	8確	10	∞
Tを確定・更新	0確	5確	3確	7確	8確	10確	∞

Sを確定すると、A＝7、B＝3、C＝11です。未確定の最小はB＝3なのでBを選びます。BからAへ行く候補は3＋2＝5で、現在の7より小さいためAを5に更新します。Cも3＋6＝9へ、Dも3＋8＝11へ更新します。Bから出る辺の重みだけを並べるのではなく、必ずBまでの3を加えます。

次はA＝5を確定します。A経由のCは5＋2＝7なので9から7へ、Dは5＋5＝10なので11から10へ変わります。ここでD＝10をすぐ確定してはいけません。未確定にはC＝7も残っているため、次に選ぶのはCです。

C＝7を確定すると、Dは7＋1＝8となり、10から8へ再更新されます。Tへの候補は7＋7＝14です。続いてD＝8を確定すると、Tは8＋2＝10へ短縮されます。最後にT＝10を確定し、目的地までの最短距離が10と分かります。

この例の確定順はS→B→A→C→D→Tです。Dの候補は∞→11→10→8、Tの候補は∞→14→10と変わりました。最終値だけでなく、この変化を説明できれば、どの行で更新条件を取り違えたかを自分で見つけられます。Uは到達不可なので∞のまま残ります。

更新表の確定距離だけを上から読むと、0・3・5・7・8・10と小さい順に並びます。この例で5のあとに3を確定した記録があれば、確定済みを再選択したか、未確定全体の最小値を探せていない可能性があります。非負重みでの確定順の確認に使える、手軽な見直し方です。

直前の頂点をたどって経路を戻す

最短距離が10と分かっても、経路が必要な問題ではもう一段階あります。距離を改善したときに記録したprevを使い、目的地Tから始点Sへ戻ります。今回の最終的な記録は、prev[T]＝D、prev[D]＝C、prev[C]＝A、prev[A]＝B、prev[B]＝Sです。

T→D→C→A→B→Sと逆向きにたどれたら、順序を反転してS→B→A→C→D→Tが答えになります。ここで逆向きにたどるのは記録の読み方であり、グラフ上の矢印を逆走してよいという意味ではありません。

検算として辺の重みを合計すると、3＋2＋2＋1＋2＝10です。復元した経路の合計が距離表の10と一致し、すべての移動方向も辺の表と一致します。距離の欄だけ正しくてprevの更新を忘れた場合は、この合計確認や矢印確認で違和感が見つかります。

なお、prevへ保存するのは経路全体でも通過頂点の個数でもなく、直前の頂点ひとつです。Cの距離を9から7へ改善したときには、Cの直前をBからAへ変更します。距離だけを書き換えて直前の記録を残すと、古い遠回りの経路を復元してしまうので、2つの更新を一組で扱いましょう。

基本情報のダイクストラ法を例題で確認する

表の誤答から原因を切り分ける

答えが合わないときは、最終距離を眺めるより、最初に正しい表と違った行を探します。下の診断表は、先ほどの独自グラフに対して起こりやすい誤りです。ひとつ前の行まで正しいかを確認してから、確定する頂点の選択と距離計算を分けて見直してください。

途中の記録・考え方	疑う原因	直す確認
Sの次にDを選ぶ	グラフ全体で重み1の辺だけを探した	SからDへの候補はまだ∞
Bの処理後にAを2とする	辺の重みを合計距離として代入した	Bまでの3を足してAは5
Aの処理後にDを確定する	直前の頂点の隣だけで選んだ	未確定全体ではC＝7が最小
Cの処理後もDが10のまま	再更新を見落とした	7＋1＝8と現在値10を比較
Tが14になった時点で終了する	候補の発見を確定と混同した	D経由で10になるまで続ける

「毎回いちばん軽い辺を選ぶ」と覚えると、Dへ入る重み1の辺が気になります。しかし、その辺の出発点Cへ行くためにもコストがかかります。比較対象は重み1そのものではなく、Cまでの7と合わせた8です。辺単体の最小と経路の合計の最小を分けてください。

また、目的地が初めて表に現れたら終了、という判断も早すぎます。Tが14になった時点では、もっと短い候補10を作るDが未確定です。目的地への距離だけが必要なら、Tが未確定全体の最小として選ばれ、確定した時点で止められます。すべての頂点の距離を問う場合は、ほかの到達可能な頂点も処理します。

最短経路の目的と、作業全体の所要期間を求める目的も区別しましょう。アローダイアグラムとクリティカルパスの計算では、先行作業の完了を待つ関係から最長の所要時間が問題になります。図に頂点と矢印があるだけで、ダイクストラ法の最小値更新をそのまま当てはめないようにします。

擬似コードは選択と更新を分けて読む

擬似コードの変数名が変わっても、距離・確定状態・直前の頂点の役割を見つければ対応できます。以下は手順を理解するための簡略例です。辺が存在しない組は反復の対象に含めず、同距離では更新しないものとしています。

辺の重みが配列や行列で与えられるときは、「辺がない」ことの表し方も確認します。特に重み0の辺を許すなら、0という値だけで辺なしと判断できません。問題が∞や特別な値、別の接続情報を使っている場合は、その約束に従って候補を計算する範囲を決めます。

すべての頂点vについて
    d[v] ← ∞
    fixed[v] ← false
    prev[v] ← 未設定
d[S] ← 0

繰り返し
    未確定の中でd[u]が最小の頂点uを選ぶ
    その頂点がない、またはd[u]が∞なら終了
    fixed[u] ← true
    uから辺が出ている各頂点vについて
        fixed[v]がfalseなら
            candidate ← d[u] + 重み(u→v)
            candidate < d[v]なら
                d[v] ← candidate
                prev[v] ← u

空欄問題では、candidateの計算に使う距離が「今回確定したuまでの距離」なのかを見ます。d[v]＋重み(u→v)では、行き先までの候補に同じ辺の重みを加えることになり、uを経由する意味が失われます。距離の添字と辺の向きは一緒に確認しましょう。

更新条件も向きが大切です。candidate＜d[v]なら、短い候補を採用しています。不等号を逆にすると長い候補を残してしまいます。確定の判定と距離の改善を同じif文だと思わず、どちらの処理を制御しているかを文章に直すと追いやすくなります。

なお、未確定の最小値を毎回すべての頂点から探す配列中心の実装では、頂点数をVとして計算量はO(V²)になります。優先度付きキューを使う実装もありますが、表を追う練習では、選択の高速化より先に「何を比較しているか」を理解する方が役立ちます。実装で計算量が変わる点は、Princeton大学の最短経路講義資料でも整理されています。

同距離・到達不可・負の辺を区別する

未確定の最小値が同じ頂点が複数ある場合、最短距離を求める目的なら、その中のどれから確定しても構いません。ただし、確定順そのものやprevの配列を答える問題では、頂点番号順や走査順など、問題文やコードに書かれた条件に従います。

例えばS→A＝2、S→B＝2、A→T＝3、B→T＝3だけがある別のグラフでは、Tまでの最短距離は5です。Aを先に処理し、同距離ではprevを書き換えないならTの直前はAになります。Bを先に処理すれば直前はBになり得ますが、どちらも正しい長さ5の経路です。経路がひとつに決まるとは限りません。

到達できない頂点は、最初の例のUのように∞のままです。未確定の頂点に有限の候補が残っていなければ、始点から新たに到達できる頂点はありません。∞の頂点を無理に経路へ加えたり、prevが未設定なのに逆向きの復元を始めたりしないでください。

負の辺は、到達不可や同距離とは違う問題です。例えばS→A＝2、S→B＝5、B→A＝−4なら、通常の手順は先にA＝2を確定します。しかし実際にはS→B→Aで5−4＝1です。遠いBを経由することで既に確定したAより短くなるため、「あとから短くならない」という根拠が崩れます。

負の辺がひとつあれば必ずすべての答えが誤る、という意味ではありません。通常のダイクストラ法では正解を保証できないので適用条件から外れる、という意味です。負の辺を扱う代表例にはベルマンフォード法がありますが、到達可能な負閉路の有無など別の条件確認も必要になります。

負の値をなくすため、すべての辺へ同じ値を足す方法にも注意が必要です。経路ごとに通る辺の数が違うと、加算される合計が違い、どの経路が最短かまで変わる場合があります。入力を自己判断で補正せず、問題文の前提と指定されたアルゴリズムを確認しましょう。

重みを変えた練習問題を解く

最後に、最初の独自グラフでB→Dの重みだけを8から3へ変更します。ほかの辺と頂点はすべて同じです。SからTまでの最短距離、確定順、最短経路を求めてください。先ほどの答え10を少し調整するのではなく、Sを始点として表を初期化し直してみましょう。

途中で確認するポイントは3つです。Bを確定した直後にDの候補はいくつか。Aを確定して更新を終えたあと、CとDのどちらを先に確定するか。DからTの候補が見つかった瞬間に処理を終えてよいか。この3点を紙に書いてから、下の解答と照合してください。

B＝3を確定すると、Dは3＋3＝6になります。同じ行のAは5、Cは9です。次にA＝5を確定してCを7へ更新しますが、Dへの候補5＋5＝10は現在値6より大きいので採用しません。したがって、その次に選ぶのはC＝7ではなくD＝6です。

D＝6を確定するとTは6＋2＝8になります。ただしC＝7が未確定なので、次はCを確定します。C経由のTは7＋7＝14で、現在値8より大きいため更新しません。最後にT＝8を確定します。

確認項目	変更後の答え
Bの処理直後のD	6
確定順	S→B→A→D→C→T
Tまでの最短距離	8
最短経路	S→B→D→T
経路の合計	3＋3＋2＝8
Uへの距離	∞（到達不可）

最終距離が8でも、確定順にCを先に書いていたら選択処理を見直します。距離を変えた辺から出る候補によって、以前と異なる頂点が先に確定されるからです。反対に、最短距離だけは正しいが経路が以前のままなら、prevを初期化し忘れたか、更新と同時に書き換え忘れた可能性があります。

さらに自分で練習するときは、辺をひとつ変えるたびに、予想・更新表・経路の合計を順に照合します。最終値の暗記では見つからない、途中の比較の理解を確認できます。複数の辺を一度に変えるより、どの変更が確定順を変えたかをひとつずつ説明できる形が向いています。

まとめ：基本情報のダイクストラ法の確認点

基本情報のダイクストラ法は、未確定の中で始点からの暫定距離が最小の頂点を確定し、その頂点を経由する候補で隣を更新する手順です。辺の重みだけを選ぶ方法と混同せず、更新時は「確定した頂点までの距離＋辺の重み」を計算します。

最初の例題はTまで10、B→Dだけを3へ変えた例題はTまで8でした。表の数値が合うだけでなく、確定順とprevから復元した経路、その合計も一致するかを確認してください。間違えたら、初めて表が違った行へ戻り、選択・足し算・比較・記録のどこでずれたかを確認しましょう。

最後に、重みは0以上か、矢印の方向を守っているか、到達できない頂点を∞のまま扱っているかを点検します。同距離の確定順は問題の指定に従うと押さえれば、表や擬似コードの見た目が変わっても同じ原理で追えるようになります。