Pythonで最短経路探索|9ノードの交通網で距離と時間の最短ルートを比べる

目的地へ行くとき、「距離が短い道」と「早く着く道」が違うことは珍しくありません。では、コンピューターは何を手がかりに、どちらの道がよいと判断するのでしょうか。

この記事では、Pythonで最短経路を計算します。はじめに実際の道路の例を眺めたあと、9つの点を3×3に並べた仮想交通網を使って、データの作り方、ダイクストラ法の考え方、距離と時間による経路の違いを順に確認します。途中で別のネットワークに切り替えず、同じ図で最後まで考えていきます。

1.実際の道路で見る「近い道」と「早い道」

まず、甲府市中心部の道路網で計算した例です。左は距離、右は仮定した所要時間を最小にする経路を示しています。

甲府市中心部の距離最短経路と仮定時間最短経路の比較地図
道路形状はOpenStreetMapの実データ。時間は教材用の仮定速度から計算した値です。© OpenStreetMap contributors(ODbL)。

この例では、距離最短が約2.884 km・5.80分、仮定した時間最短が約2.890 km・4.96分となりました。少し長い道でも、道路ごとに設定した速度が違えば、時間は短くなります。ただし、実測結果ではなく、信号待ちや渋滞も含めていません。

実道路には一方通行や複雑な交差点があり、仕組みの説明とデータの準備が混ざりがちです。そこで、ここからはつながりを一目で追える仮想交通網に絞ります。実道路のデータとコードは、最後に発展教材として残しています。

2.9ノードの交通網を、点・線・重みで表す

交差点などの点をノード、点と点を結ぶ道路区間をリンク(エッジ)と呼びます。この点と線のつながりがグラフです。今回はAからIまで9つのノードを用意し、上下左右の隣同士を12本のリンクで結びます。出発点はA、目的地はIです。

AからIまでを3×3に並べた9ノード12リンクの交通網。各区間に距離と時間を表示。
ラベルは「距離(km)/時間(分)」。すべて双方向で、往復の値は同じです。正方形の配置は模式図で、描いた線の長さは実距離を表しません。

リンクに与えた距離や時間を重み(コスト)と呼びます。「最短」とは、通るリンクの重みを足し合わせ、その合計が最も小さいという意味です。距離を重みにすれば距離最短、時間を重みにすれば時間最短を求められます。

この教材では、上側・右側の外周は「短いけれど時間がかかる道路」、左側・下側の外周は「距離は長いけれど早く通れる道路」に設定しました。中央を通る道も含めて、すべての入力値は次のとおりです。

リンク(双方向)距離(km)時間(分)
A–B13
B–C13
C–F13
F–I13
A–D1.51.5
D–G1.51.5
G–H1.51.5
H–I1.51.5
B–E25
D–E25
E–F25
E–H25

時間は教材用に直接与えた固定値です。実際の道路の観測値ではなく、車が増えても変わらないものとします。まずは道路のつながりと重みが与えられたとき、どの経路が最短かという問題だけを解きます。

3.ダイクストラ法は、出発点からの合計を比べる

ダイクストラ法は、出発点からの合計コストが最も小さい未確定のノードを選び、そこまでの最短コストを確定して、隣のノードへ行く候補を更新する方法です。目の前の短いリンクだけを選び続ける方法ではありません。

同じ9ノードの図を使い、距離で考えます。はじめはAまでが0 km、ほかはまだ行き方が分からないので∞とします。

  1. Aを確定します。隣のBは1 km、Dは1.5 kmで行ける候補になります。
  2. 未確定の候補で最小のB(1 km)を確定します。B経由ならCは2 km、Eは3 kmです。
  3. 次はD(1.5 km)です。Gは3 kmになります。Eへの候補は1.5+2=3.5 kmなので、すでに見つけた3 kmを残します。
  4. C(2 km)を確定すると、Fは3 kmになります。
  5. 3 kmの候補を順に調べます。FからIへ進む候補は3+1=4 kmです。
  6. Iの4 kmより小さい未確定の候補がなくなったところで、Iまでの最短距離が確定します。

途中の記録をまとめると次のようになります。同じ距離の候補はどれから調べても最短距離は変わりません。この表ではノード名順に処理しています。「候補」は、確定前にはより短い値に更新される可能性があります。

確定した点Aからの距離(km)新しい候補・改善した候補
A0B=1、D=1.5
B1C=2、E=3
D1.5G=3(Eは3を維持)
C2F=3
E3H=5
F3I=4
G3Hを5から4.5へ更新
I4目的地までの最短距離が確定

どのノードを経由してその値になったかも記録しておくと、I←F←C←B←Aと戻れます。向きを直せば、距離最短の経路はA→B→C→F→Iです。

今回は距離がすべて正なので、この方法を使えます。ダイクストラ法の前提は重みが非負であることです。時間最短でも、合計する項目を距離から時間に替えるだけで、同じ考え方が使えます。

4.CSVとPythonコードをダウンロードする

9ノード交通網の教材一式をダウンロード(ZIP)

本文と同じ入力データ、計算コード、図を作るコード、生成済みの結果を同梱しています。道路データの取得やAPIキーは不要です。

ファイル役割
links.csv12リンクの始点・終点・距離・時間
calculate_routes.py次章に載せた短い計算コード
run_grid.py図の作成・探索履歴の保存・最短経路の検算
requirements.txtライブラリの確認済みバージョン
results/図3枚、経路比較CSV、探索履歴CSV、検算結果JSON
README.txt/LICENSE使い方、モデルの前提、利用条件

CSVの1行は1本の双方向リンクを表します。たとえばA,B,1,3は「AとBの間は1 km・3分」です。逆向きも同じ値なので、B,Aを別の行に書く必要はありません。

u,v,distance_km,time_min
A,B,1,3
B,C,1,3
C,F,1,3
F,I,1,3
A,D,1.5,1.5
D,G,1.5,1.5
G,H,1.5,1.5
H,I,1.5,1.5
B,E,2,5
D,E,2,5
E,F,2,5
E,H,2,5

検証環境はPython 3.11.5、NetworkX 3.1、Matplotlib 3.7.2、NumPy 1.24.3です。ZIPを展開し、grid-network-kitフォルダーをターミナルで開いて実行します。Windows PowerShellなら次のとおりです。

python -m venv .venv
.venv\Scripts\python.exe -m pip install -r requirements.txt
.venv\Scripts\python.exe calculate_routes.py
.venv\Scripts\python.exe run_grid.py

macOS・Linuxではpythonをpython3、.venv\Scripts\python.exeを.venv/bin/pythonに置き換えてください。初回のライブラリ取得にはインターネットが必要です。以降の計算は同梱データだけで実行できます。

5.Pythonで距離最短と時間最短を計算する

計算の中心は次のコードです。calculate_routes.pyとして同梱しているので、まずそのまま実行できます。CSVはコードと同じフォルダーに置いてください。

from pathlib import Path
import csv
import networkx as nx

G = nx.Graph()  # 双方向。逆向きも同じ距離と時間。
csv_path = Path(__file__).resolve().parent / 'links.csv'
with csv_path.open(encoding='utf-8-sig', newline='') as f:
    for row in csv.DictReader(f):
        G.add_edge(row['u'], row['v'],
                   distance_km=float(row['distance_km']),
                   time_min=float(row['time_min']))

for label, weight in [('距離最短', 'distance_km'), ('時間最短', 'time_min')]:
    route = nx.dijkstra_path(G, 'A', 'I', weight=weight)
    distance = nx.path_weight(G, route, weight='distance_km')
    time = nx.path_weight(G, route, weight='time_min')
    print(label, ' → '.join(route), f'{distance:g} km / {time:g} 分')

nx.Graph()は、向きのないグラフを作ります。A–Bを登録すれば、AからBへもBからAへも進めます。一方通行を表したい場合は、向きのある別の構造が必要ですが、この教材は双方向で統一しています。

各リンクにはdistance_kmとtime_minの2つの属性を登録します。nx.dijkstra_pathのweightにどちらを指定するかで、最小にする対象が変わります。nx.path_weightは、見つけた経路について指定した属性を足し合わせる関数です。

ここで大事なのは、距離最短の経路の時間を合計しただけでは、時間最短を探したことにはならないという点です。時間最短を知るには、time_minを重みにして探索し直します。

実行結果は次のようになります。

距離最短 A → B → C → F → I 4 km / 12 分
時間最短 A → D → G → H → I 6 km / 6 分

図も再現する場合はrun_grid.pyを実行します。resultsフォルダーに図と集計表が出力されます。コードではAからIへ至る、同じ点を繰り返さない経路を全12本列挙し、それぞれの合計と照合しています。この小さな交通網では、距離・時間とも上の経路が一意に最短になります。大規模な道路網で全経路を列挙するための実装ではなく、教材の検算のための処理です。

6.図で比較する:4 km・12分と6 km・6分

距離を最小にすると、上側から右側へ進む

距離最短のA-B-C-F-Iを青緑で強調。合計4 km、12分。
距離最短:A→B→C→F→I。距離は1+1+1+1=4 km、時間は3+3+3+3=12分。

1 kmのリンクを4本通るため、距離は4 kmです。ただし、それぞれに3分かかるので、合計時間は12分になります。

時間を最小にすると、左側から下側へ進む

時間最短のA-D-G-H-Iをオレンジで強調。合計6 km、6分。
時間最短:A→D→G→H→I。距離は1.5×4=6 km、時間は1.5×4=6分。

こちらのリンクは1本1.5 kmあるので、合計距離は6 kmです。その代わり、1本を1.5分で通れる設定のため、合計時間は6分になります。

選ぶ基準経路距離時間
距離最短A→B→C→F→I4 km12分
時間最短A→D→G→H→I6 km6分

この条件なら、2 km遠回りすると、時間を6分短縮できます。リンク数はどちらも4本ですが、重みの合計は違います。中央のEを通る経路も探索の対象に含まれ、そのうえで上の2経路が選ばれています。

距離と時間のどちらが正しいのか、という問題ではありません。「移動距離を抑えたい」「早く到着したい」など、目的に応じて最小にする項目を選びます。また、道路ごとの時間設定が違えば経路も変わります。距離最短と時間最短が必ず異なるわけではありません。

数値を変えて試してみる

links.csvでA–Bのtime_minだけを小さくしてみてください。距離はそのままなので距離最短の条件は変わりませんが、時間最短の候補の比較は変わります。1本の時間を少し短くしただけでは、経路全体の優劣が入れ替わらないことも確かめられます。

変更後の比較はcalculate_routes.pyで行えます。run_grid.pyは元の教材の経路・合計を検算するための固定チェックも含むので、入力を変更すると検算で停止することがあります。また、図の見出しの合計値は元の教材用です。自分の条件で図を作る場合は、チェックと見出しも合わせて変更してください。

うまく動かないとき

  • ModuleNotFoundError:ライブラリを入れたPythonと、実行するPythonが同じか確認します。
  • links.csvが見つからない:ZIPを展開し、CSVをコードと同じフォルダーに置きます。
  • 図の日本語が表示されない:run_grid.pyのMeiryoを、PCに入っている日本語フォント名へ変更します。経路計算の数値には影響しません。

7.次は「誰が何台、その道路を通るのか」へ

今回は、AからIへ移動する1組の起終点について、固定の距離・時間で経路を求めました。ここには、車の台数も道路の容量も、混雑で時間が延びる仕組みも入っていません。

次は、同じ仮想交通網に「どこからどこへ何台移動するか」というOD交通量を与えます。それぞれの移動を経路に載せ、リンク別の交通量を集計するのが交通配分です。まず固定の時間で配分し、そのあと交通量によって所要時間が変わる関係を加えて、利用者均衡へ進みます。

同じ図を土台にし、OD表や容量などの仮定を一つずつ足していくと、何が結果を変えたのかを追いやすくなります。

続編「利用者均衡配分【前編】」は2026年11月20日9時(日本時間)公開予定です。公開日時以降はこちらから続編へ進めます。

発展:冒頭の実道路データでも試したい方へ

甲府の実道路データ・Pythonコードをダウンロード(ZIP・約1.5 MB)

こちらは冒頭の地図を再現する別教材です。道路CSV、元のOpenStreetMapデータ、取得条件、地図作成コード、READMEを含みます。2026年11月12日に取得したデータで、時間は道路種別ごとの仮定速度から計算しています。一方通行などを扱うため、本文の仮想交通網とはデータ構造が異なります。

信号待ち、混雑、右左折禁止などのすべての通行条件は反映していません。現実の所要時間や通行可否を保証するものではなく、分析学習用です。実データの利用条件は同梱文書とOpenStreetMapの著作権・ライセンスをご確認ください。

参考資料

コメント

タイトルとURLをコピーしました