ゆめさくエンジニア研究所女性向けエンジニアスクール女性向けエンジニアスクール
ログイン

ダイクストラ法と最短経路

回 2-8　道 2 データ構造とアルゴリズム

ダイクストラ法は、出発点から各点までの最短経路を、まだ確定していない点のうち一番近い点を 1 つずつ確定しながら求める方法です。乗り換え案内のように、駅を点、駅と駅をつなぐ線路を線、所要の分を線の重みにすると、この頁の例では本町から空港までの最短が丘と川を通る 11 分と出ます。線の重みに負の数があると、確定した点を後から直さないため、誤った答えを出します。

目安 50 分2-8 (2-0〜2-10 の中)

読み終えたら乗り換え案内のような問題を、点と線に直して解ける

この頁の流れ

  1. 1本町から空港まで、一番早い行き方をどう求めるか
  2. 2ダイクストラ法はどう最短経路を求めるのか
  3. 3動かして確かめる
  4. 4ダイクストラ法はどこで崩れるのか
  5. 5ダイクストラ法は仕事でどう確かめるのか
  6. 6関わる実例
  7. 7よくある問い
  8. 8確認クイズ
  9. 9説明課題
  10. 10もっと深く
  11. 11一次資料
  12. 12次へ

乗り換え案内のような問題を点と線に直し、線の本数で比べるのか、重みの合計で比べるのかを切り分けられるようになります。

文 ゆめさくコード編集部公開 2026年10月26日更新 2026年10月26日出典を確かめた日 2026年10月26日

本町から空港まで、一番早い行き方をどう求めるか

一番早い行き方は、駅を点、線路を線、所要の分を線の重みにして、出発の駅から近い駅を 1 つずつ確定していけば求まります。この手順がダイクストラ法です。

本町から空港へは直通の線がありますが、18 分かかります。丘で乗り換えて川を回ると、線は 3 本に増えますが合計は 11 分です。乗り換えが少ない道が、早い道とは限りません。

駅が 5 つなら道を全部書き出して比べられますが、駅が増えると道の数は一気に増えます。全部を比べずに、一番短い道だけを見つける手順が要ります。

この回では、駅と分を点と線に直し、ダイクストラ法を Python で書いて最短の分と経路を出します。

駅を点、線路を線で表し、つながりをたどって A から D への最短の道を探す図

ダイクストラ法はどう最短経路を求めるのか

ダイクストラ法は、出発点からの距離が一番小さい点を確定し、その隣の距離を書き直すことを、すべての点が確定するまで繰り返します。まずグラフ (点と線のつながり) の持ち方から見ます。

点と線と重みで、駅と線路を表す

グラフは、点 (頂点) と、点どうしをつなぐ線 (辺) でできています。線に「所要の分」のような数を付けた物を重み付きのグラフと呼び、その数を重みと呼びます。最短経路問題は、出発点から目的の点まで、重みの合計が一番小さい道を探す問題です。

この回の例は次の 7 本の線です。どの線も上りと下りで同じ分だけかかるとします。

駅駅分
本町港5
本町丘2
丘港2
港空港10
丘川6
川空港3
本町空港18

プログラムでは、点ごとに「隣の点と重み」の一覧 (隣接リスト) を持ちます。本町の一覧は、港へ 5 分、丘へ 2 分、空港へ 18 分です。上りと下りのある線は、行きと帰りの 2 本の向きのある線として両方の駅の一覧に入れるので、7 本の線は 14 本になります。

一番近い点を確定し、隣を書き直す

手順は次の通りです。

  1. 出発点の距離を 0、ほかの点の距離を無限大 (まだ行き方を知らない印) にする
  2. まだ確定していない点のうち、距離が一番小さい点を選び、確定する
  3. 確定した点の隣について、「確定した点の距離 + 線の重み」が今の距離より小さければ、距離を書き直し、どこから来たか (前の点) を覚える
  4. すべての点が確定するまで 2 と 3 を繰り返す

確定とは「この点への距離は、もうこれより短くならない」と決めることです。線の重みが 0 以上なら、回り道は重みを足すだけで減らさないので、そう決めてよいのです。

辺 1 本より辺 2 本が短いことがある

一番近い点を、ヒープで速く取り出す

手順の 2 で毎回全部の点を見比べると手間がかかるので、2-4 の回で触れた優先度付きキュー (小さい物から先に出すキュー) を使います。Python では標準の heapq で作れます。

heapq の公式文書は、ヒープでは一番小さい物がいつも heap[0] にあり、heappop は一番小さい物を取り出すと書いています。中身に (距離, 点) の組を入れると、距離の小さい順に出てきます。

公式文書は、入れた物の優先度を変えるのはヒープの並びを崩すので難しいとし、古い物は残したまま新しい物を入れ直す方法を示しています。ダイクストラ法でも、短い道が見つかるたびに新しい札を入れ、取り出した札の点がもう確定していれば、古い札として捨てます。

幅優先探索とどう違うのか

幅優先探索 (BFS) は、線の重みが全部同じときの最短経路を求める方法で、ダイクストラ法の特別な場合と見られます。重みが全部 1 なら、「重みの合計」は「線の本数」と同じになるからです。

探し方線の重み出す答え使う入れ物
幅優先探索全部同じ線の本数が一番少ない道キュー (deque)
ダイクストラ法0 以上重みの合計が一番小さい道優先度付きキュー (heapq)
ベルマン・フォード法負もよい重みの合計が一番小さい道線の一覧を何度も見直す
深さ優先探索見ない行けるかどうか (最短とは限らない)スタック

深さ優先探索は深く進んでから戻る探し方で、最初に見つけた道が最短とは限りません。

動かして確かめる

1 本目は、本町から出発し、確定、更新、捨てる札を 1 行ずつ出します。最後に経路と、入れた札と向きのある線の数を出します。inf は math.inf で、公式文書では正の無限大です。

動かす 乗り換え案内をダイクストラ法で解く

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

確定 本町 0
  更新 港 inf → 5
  更新 丘 inf → 2
  更新 空港 inf → 18
確定 丘 2
  更新 港 5 → 4
  更新 川 inf → 8
確定 港 4
  更新 空港 18 → 14
  捨てる 港 5
確定 川 8
  更新 空港 14 → 11
確定 空港 11
  捨てる 空港 14
  捨てる 空港 18
本町→丘→川→空港
札 8 線 14

最初に本町を 0 分で確定すると、隣の港、丘、空港が 5、2、18 分に書き直されます。次に一番近いのは丘の 2 分なので、丘を確定します。丘を通ると港へは 2 + 2 で 4 分になり、5 分から 4 分に縮みます。

空港は直通の 18 分、港を回る 14 分、川を回る 11 分と 3 回書き直されました。空港の札は 3 枚ヒープに入り、11 分の札が先に出て確定し、あとの 14 分と 18 分の札は捨てられます。

経路は、空港の前の点 (川)、その前 (丘)、その前 (本町) と後ろからたどって逆に並べます。この前の点の記録を、最短経路の木と呼びます。

入れた札は最初の 1 枚を含めて 8 枚です。札を入れるのは線をたどって距離が縮んだときだけなので、札は「線の数 + 1」、ここでは 14 + 1 を超えません。

BFS は距離の層でひろがる

2 本目は、同じ図を幅優先探索とダイクストラ法で解き比べ、重みを全部 1 にしたとき答えが同じになるかを見ます。列は駅、線の本数、分です。

動かす 幅優先探索とダイクストラ法を比べる

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

駅 線の本数 分
本町 0 0
港 1 4
丘 1 2
空港 1 11
川 2 8
全部 1 で同じ True

幅優先探索では空港は線 1 本 (18 分の直通) ですが、ダイクストラ法の 11 分の道は線 3 本です。港も、直通の 5 分より丘を回る 4 分が早いです。幅優先探索は線の本数を数えるので、重みが違う線が混ざると早い道を見落とします。

重みを全部 1 にすると、2 つの答えは全部の駅で同じになりました。幅優先探索は、近い順に 1 層ずつ広げることで、「一番近い点から確定する」をキューだけで済ませています。

ダイクストラ法はどこで崩れるのか

ダイクストラ法は、線の重みに負の数があると、誤った答えを出します。確定した点を後から直さないという決まりが、重みが 0 以上であることを前提にしているからです。

負の重みの線があると、確定が早すぎる

次のコードは、B から A への線だけが -4 の図を解き、ダイクストラ法の答えと、道を全部たどった正しい答えを並べます。縮んだ数は、確定したあとでもっと短い道が見つかった数です。後半は、負の線を 4 に替えて同じことをします。

動かす 負の重みの線で答えを誤る

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

点 求めた 正しい
A 2 1
B 5 5
C 3 2
縮んだ数 1
点 求めた 正しい
A 2 2
B 5 5
C 3 3
縮んだ数 0

負の線があるとき、ダイクストラ法は A を 2、C を 3 と答えました。正しくは、S から B へ 5、B から A へ -4 で、A は 1 です。C も A を通るので 2 です。

順に追うと、A (2)、C (3)、B (5) の順に確定し、最後に B から A へ 5 + (-4) で 1 の道が見つかります。しかし A はもう確定しているので書き直さず、A を通る C も 3 のまま残ります。縮んだ数の 1 は、この見落としです。

負の線を 4 に替えると、答えは全部の点で一致し、縮んだ数は 0 です。負の重みの線がある図では、ダイクストラ法の代わりに、ベルマン・フォード法 (線の一覧を何度も見直して距離を縮める方法) を使います。

なぜ確定した点を後から直さなくてよいのか

重みが 0 以上なら、確定した点にもっと短い道があとから見つかることは起こりません。だから直す手間を省けて、速く済みます。

ある点 X を確定する瞬間を考えます。X の距離 d は、まだ確定していない点の中で一番小さい値です。X へのほかの道は、どこかで未確定の点 Y を通ります。Y までの距離は d 以上で、Y から X までの線の重みは 0 以上なので、その道の合計も d 以上です。d より短い道は作れません。

負の線は、足すと合計が減るので、この理屈を崩します。上のコードで負の線のときだけ縮んだ数が 1 になったのは、そのためです。

ダイクストラ法は仕事でどう確かめるのか

仕事では、重みが 0 以上かを先に確かめ、小さな図では全部たどった答えと突き合わせ、出した経路の重みを足し直します。

  1. 図を作るときに、線の重みが全部 0 以上かを確かめる。負の数が混ざるなら、ダイクストラ法を使わない
  2. 重みが全部同じなら、幅優先探索で足りる。ヒープを使うのは重みが違うときだけにする
  3. 試験では、小さな図で、上の brute のように全部たどった答えと一致するかを見る
  4. 出した経路の線の重みを足し直し、求めた距離と同じかを見る
  5. 行けない点の距離は無限大のまま残るので、その場合の表示を決めておく

ダイクストラ法の試験

def test_weights_not_negative():
    for a, b, m in lines:
        assert m >= 0, (a, b)


def test_route_sum():
    total = 0
    for x, y in zip(p, p[1:]):
        total += dict(adj[x])[y]
    assert total == dist["空港"]

関わる実例

1956年、64 の都市の地図で最短の道を見せた

Communications of the ACM の 2010年8月号 (Vol. 53 No. 8) が載せた Dijkstra 本人の聞き取りによると、Dijkstra は 1956年、計算機 ARMAC のお披露目で、計算機を知らない人にも分かる問題として、オランダの都市の間の最短の道を求めるプログラムを作りました。地図は 64 の都市に減らし、都市を 6 ビットで表しました。手順はカフェのテラスで、紙も鉛筆も使わずに約 20 分で考えたと語っています。

発表は 1959年の Numerische Mathematik 第 1 巻で、当時は「行き方は有限個で、一番短い物があるのは明らかなのに、何を騒ぐのか」と、数学と見なされなかったそうです。崩れた前提は「有限個なら最短は簡単に求まる」です。行き方の数は都市が増えると一気に増え、全部を比べずに最短だけを見つける手順が要りました。本人も、今では旅の経路を調べる道具や車の道案内で広く使われていると述べています。

出典は An Interview with Edsger W. Dijkstra (Communications of the ACM) と A note on two problems in connexion with graphs (Numerische Mathematik) です。

OSPF は、線の重みを 0 より大きく決めている (1998年4月)

1998年4月の RFC 2328 は、インターネットの通り道を決める仕組み OSPF の第 2 版の仕様です。各ルーター (通り道を振り分ける機械) は、つながりの情報を向きのあるグラフとして持ち、自分を根とする最短経路の木をダイクストラ法で作ると書かれています (16.1 節)。

同じ仕様は、各つなぎ口の重み (送るときのコスト) を 0 より大きくしなければならないと決めています。ダイクストラ法が頼る「重みは 0 以上」という前提を、仕様の側で守っている形です。

出典は RFC 2328 OSPF Version 2 (RFC Editor) です。

よくある問い

ダイクストラ法の計算量はどのくらいですか

点の数を V、線の数を E とすると、ヒープを使うダイクストラ法は O((V + E) log V) と書きます。札の出し入れは上のコードの通り線の数ほどに収まり、heapq の公式文書は 1 回の取り出しの手間が中身の数の log に比例すると書いています。

幅優先探索 (BFS) とダイクストラ法はどう使い分けますか

線の重みが全部同じなら幅優先探索、重みが違って 0 以上ならダイクストラ法です。乗り換えの回数を減らしたいなら幅優先探索、所要の分や運賃を小さくしたいならダイクストラ法を使います。

最短経路の簡単な解き方はありますか

点が数個なら、上の brute のように道を全部たどるのが一番簡単です。ただ点が増えると道の数が一気に増えるので、試験の突き合わせ用に限ります。重みが全部同じなら、幅優先探索が簡単に書けます。

すべての駅の組の最短を出すにはどうしますか

重みが 0 以上なら、出発点を替えてダイクストラ法を点の数だけ回せば出ます。すべての組を一度に求めるワーシャル・フロイド法もあります。1 回に 1 組だけ聞かれるなら、目的の駅が確定した所で止めれば足ります。

確認クイズ

答えだと思う選択肢を押すと、その場で正誤と理由が開きます。4 問すべてに正しく答えると、この回は修了で、石が緑に変わります (この端末のブラウザに残ります)。間違えた問いは、あとから解き直せます。

1 問目

所要の分の合計が一番小さい行き方を求めます。線の重み (分) はどれも 1 以上です。向いている方法はどれですか。

2 問目

このコードを動かすと何が出ますか。

小さな図のダイクストラ法

from heapq import heappop
from heapq import heappush

adj = {
    "A": [("B", 4), ("C", 1)],
    "B": [],
    "C": [("B", 2)],
}
dist = {"A": 0}
h = [(0, "A")]
while h:
    d, u = heappop(h)
    for v, w in adj[u]:
        nd = d + w
        if nd < dist.get(v, 99):
            dist[v] = nd
            heappush(h, (nd, v))
print(dist["B"])

3 問目

ダイクストラ法で、ある点を確定したあと、その点の距離を後から直さなくてよいのはなぜですか。

4 問目

線 S→A が 2、S→B が 5、B→A が -4 の図で、ダイクストラ法を使うと A の距離はいくつと出ますか。

説明課題

乗り換え案内で「本町から空港まで一番早い行き方」を求める手順を、「点」「線」「重み」「確定」という言葉を使って 4 文以内で説明してください。重みに負の数があるとどうなるかも 1 文入れてください。書いたら、下の模範解答を開いて比べてください。

模範解答

自分の説明を書いてから開いて、比べてください。

この回の先の一歩

経路の探索、作業の依存の順番、ネットワークの道選びは、点と線に直すと同じ形の問題として解けます。いまの自分が転職までの道のどの段にいるかは、転職診断で確かめられます。

もっと深く

この回の続きを、ゆめさくのコースの章や道具で深められます。頁の中の確認クイズに答えたあと、手を動かす量を増やしたいときに使ってください。

一次資料

どれも 2026年10月26日に開いて、題と中身を確かめました。

次へ

前の回 2-7ハッシュテーブル鍵から一気に引く、衝突次の回 2-9動的計画法同じ計算を 2 度しない

道 2 データ構造とアルゴリズムの回

  1. 2-0アルゴリズムとは順次、分岐、反復の 3 つで書く手順頁で読む
  2. 2-1線形探索と二分探索100 万件でも 20 回で見つかる頁で読む
  3. 2-2バブルソートと挿入・選択ソート遅いソート 3 つ、2 倍で約 4 倍頁で読む
  4. 2-3クイックソートとマージソート速いソート 2 つ、平均と最悪頁で読む
  5. 2-4スタックとキュー積む順と並ぶ順頁で読む
  6. 2-5再帰自分を呼んで小さくする頁で読む
  7. 2-6木と二分探索木たどる順、片寄り頁で読む
  8. 2-7ハッシュテーブル鍵から一気に引く、衝突頁で読む
  9. 2-8ダイクストラ法と最短経路点と線、幅優先、重みのある道この回
  10. 2-9動的計画法同じ計算を 2 度しない頁で読む
  11. 2-10試験と面接で確かめる基本情報 科目B、道場 10 問、面接 20 問頁で読む

道 2 の頁へ戻るほかの道を見る