目的地へ行くとき、「距離が短い道」と「早く着く道」が違うことは珍しくありません。では、コンピューターは何を手がかりに、どちらの道がよいと判断するのでしょうか。
この記事では、Pythonで最短経路を計算します。はじめに実際の道路の例を眺めたあと、9つの点を3×3に並べた仮想交通網を使って、データの作り方、ダイクストラ法の考え方、距離と時間による経路の違いを順に確認します。途中で別のネットワークに切り替えず、同じ図で最後まで考えていきます。
1.実際の道路で見る「近い道」と「早い道」
まず、甲府市中心部の道路網で計算した例です。左は距離、右は仮定した所要時間を最小にする経路を示しています。

この例では、距離最短が約2.884 km・5.80分、仮定した時間最短が約2.890 km・4.96分となりました。少し長い道でも、道路ごとに設定した速度が違えば、時間は短くなります。ただし、実測結果ではなく、信号待ちや渋滞も含めていません。
実道路には一方通行や複雑な交差点があり、仕組みの説明とデータの準備が混ざりがちです。そこで、ここからはつながりを一目で追える仮想交通網に絞ります。実道路のデータとコードは、最後に発展教材として残しています。
2.9ノードの交通網を、点・線・重みで表す
交差点などの点をノード、点と点を結ぶ道路区間をリンク(エッジ)と呼びます。この点と線のつながりがグラフです。今回はAからIまで9つのノードを用意し、上下左右の隣同士を12本のリンクで結びます。出発点はA、目的地はIです。

リンクに与えた距離や時間を重み(コスト)と呼びます。「最短」とは、通るリンクの重みを足し合わせ、その合計が最も小さいという意味です。距離を重みにすれば距離最短、時間を重みにすれば時間最短を求められます。
この教材では、上側・右側の外周は「短いけれど時間がかかる道路」、左側・下側の外周は「距離は長いけれど早く通れる道路」に設定しました。中央を通る道も含めて、すべての入力値は次のとおりです。
| リンク(双方向) | 距離(km) | 時間(分) |
|---|---|---|
| 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 |
時間は教材用に直接与えた固定値です。実際の道路の観測値ではなく、車が増えても変わらないものとします。まずは道路のつながりと重みが与えられたとき、どの経路が最短かという問題だけを解きます。
3.ダイクストラ法は、出発点からの合計を比べる
ダイクストラ法は、出発点からの合計コストが最も小さい未確定のノードを選び、そこまでの最短コストを確定して、隣のノードへ行く候補を更新する方法です。目の前の短いリンクだけを選び続ける方法ではありません。
同じ9ノードの図を使い、距離で考えます。はじめはAまでが0 km、ほかはまだ行き方が分からないので∞とします。
- Aを確定します。隣のBは1 km、Dは1.5 kmで行ける候補になります。
- 未確定の候補で最小のB(1 km)を確定します。B経由ならCは2 km、Eは3 kmです。
- 次はD(1.5 km)です。Gは3 kmになります。Eへの候補は1.5+2=3.5 kmなので、すでに見つけた3 kmを残します。
- C(2 km)を確定すると、Fは3 kmになります。
- 3 kmの候補を順に調べます。FからIへ進む候補は3+1=4 kmです。
- Iの4 kmより小さい未確定の候補がなくなったところで、Iまでの最短距離が確定します。
途中の記録をまとめると次のようになります。同じ距離の候補はどれから調べても最短距離は変わりません。この表ではノード名順に処理しています。「候補」は、確定前にはより短い値に更新される可能性があります。
| 確定した点 | Aからの距離(km) | 新しい候補・改善した候補 |
|---|---|---|
| A | 0 | B=1、D=1.5 |
| B | 1 | C=2、E=3 |
| D | 1.5 | G=3(Eは3を維持) |
| C | 2 | F=3 |
| E | 3 | H=5 |
| F | 3 | I=4 |
| G | 3 | Hを5から4.5へ更新 |
| I | 4 | 目的地までの最短距離が確定 |
どのノードを経由してその値になったかも記録しておくと、I←F←C←B←Aと戻れます。向きを直せば、距離最短の経路はA→B→C→F→Iです。
今回は距離がすべて正なので、この方法を使えます。ダイクストラ法の前提は重みが非負であることです。時間最短でも、合計する項目を距離から時間に替えるだけで、同じ考え方が使えます。
4.CSVとPythonコードをダウンロードする
本文と同じ入力データ、計算コード、図を作るコード、生成済みの結果を同梱しています。道路データの取得やAPIキーは不要です。
| ファイル | 役割 |
|---|---|
| links.csv | 12リンクの始点・終点・距離・時間 |
| 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分
距離を最小にすると、上側から右側へ進む

1 kmのリンクを4本通るため、距離は4 kmです。ただし、それぞれに3分かかるので、合計時間は12分になります。
時間を最小にすると、左側から下側へ進む

こちらのリンクは1本1.5 kmあるので、合計距離は6 kmです。その代わり、1本を1.5分で通れる設定のため、合計時間は6分になります。
| 選ぶ基準 | 経路 | 距離 | 時間 |
|---|---|---|---|
| 距離最短 | A→B→C→F→I | 4 km | 12分 |
| 時間最短 | A→D→G→H→I | 6 km | 6分 |
この条件なら、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の著作権・ライセンスをご確認ください。
参考資料
- NetworkX公式:dijkstra_path(教材の実行確認版は3.1)
- OpenStreetMap:著作権とライセンス/ODbL 1.0(冒頭の実道路データ)


コメント