山手線でグラフ理論 ダイクストラ法を試す。

20210415_都会を走る山手線_E235系

グラフ理論のダイクストラ法は基本的部分であるけれど取っつきにくかった。
リンクをたどり最短で目的地到達とか、到達距離とか時間を計算する手法が
グラフ理論なのだけれど、数字ばかりで論理的理解では理解できるものの
エモーショナルな部分で??と腑に落ちていなかったので、エモーショナル
部分でも感応できるように、山手線+αのグラフとSciPyのダイクストラ法を
試してみたいと思います。


プログラム仕様

各駅を点として山手線、中央線、京浜東北線などをグラフ化し、これで目的地
までの時間など試します。
試すファンクションはscipy.sparse.csgraphdijkstraを使います。
詳細は下記リンクを参照。
  SciPy.org - scipy.sparse.csgraph.dijkstra

山手線+αグラフ
20210415_csg.png

駅コード
コード
東京0
神田1
上野2
日暮里3
池袋4
渋谷5
品川6
新宿7
川崎8
横浜9


駅区間移動時間(分)
移動時間(分)
東京品川8
品川渋谷13
渋谷新宿6
新宿神田12
東京神田2
神田上野5
上野日暮里4
日暮里池袋12
池袋新宿6
品川川崎14
川崎横浜12




Pythonサンプルプログラム

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import pprint

# 駅
station_def = ['東京','神田','上野','日暮里',
'池袋','渋谷', '品川','新宿', '川崎','横浜']

# 区間データ
Station_section = [
['東京', '品川', 8],
['品川', '渋谷', 13],
['渋谷', '新宿', 6],
['新宿', '神田', 12],
['東京', '神田', 2],
['神田', '上野', 5],
['上野', '日暮里', 4],
['日暮里', '池袋', 12],
['池袋', '新宿', 6],
['品川', '川崎', 14],
['川崎', '横浜', 12]]

# 駅コード辞書登録
stations_no, stations_name = {}, {}
for i, s in enumerate(station_def):
stations_no[s] = i
stations_name[i] = s
print(s, i)

# 駅区間データの生成
section = []
for ss in Station_section:
st1 = stations_no[ss[0]]
st2 = stations_no[ss[1]]
section.append([st1, ss[0], st2, ss[1],ss[2]])
section.append([st2, ss[1], st1, ss[0], ss[2]])
section = np.array(section)
pprint.pprint(section)

# csr_matrixの生成
row = np.array(section[:,0].astype(np.int32))
col = np.array(section[:,2].astype(np.int32))
data = np.array(section[:,4].astype(np.float64))
N = max(np.max(row), np.max(col)) + 1
print('N=', N)

graph = csr_matrix((data, (row, col)), shape=(N, N))
print('{}\n'.format(graph.toarray()))

start_st_indx = [0, 9]

# ダイクストラ法
distance_mat, processors = dijkstra(graph, directed = False, indices =start_st_indx, return_predecessors = True)
print('始点からの最短時間(分)')
print('{}\n'.format(distance_mat))
print('各駅の直前の駅')
print('{}\n'.format(processors))

for stidx, st in enumerate(start_st_indx):
# 最短時間
print('%d:%s駅からの最短時間(分)'%(stidx+1,stations_name[st]))
for i, d in enumerate(distance_mat[stidx]):
print(' {0}({1}) --> {2}({3}) {4}分'.format(stations_name[st], st, stations_name[i],i, d))

# 各駅の直前の駅
print ('\n 各駅の直前の駅')
for i, d in enumerate(processors[stidx]):
if 0 <= d:
print(' {0}({1}) <-- {2}({3})'.format(stations_name[i], i, stations_name[d], d))
print()

プログラムは東京(0)駅発と横浜(0)駅発を計算します。
なお、鈍行の移動時間だけで計算し、駅での停車時間、
快速、湘南新宿ラインなどは除外しています。
dijkstra()のパラメータindicesに開始駅のコードを入力します。


動作環境

Windows Anaconda (Miniforge3)
Python 3.9.2 packaged by conda-forge
scipy 1.6.2


結果


東京駅発


1:東京駅からの最短時間(分)
東京(0) --> 東京(0) 0.0分
東京(0) --> 神田(1) 2.0分
東京(0) --> 上野(2) 7.0分
東京(0) --> 日暮里(3) 11.0分
東京(0) --> 池袋(4) 20.0分
東京(0) --> 渋谷(5) 20.0分
東京(0) --> 品川(6) 8.0分
東京(0) --> 新宿(7) 14.0分
東京(0) --> 川崎(8) 22.0分
東京(0) --> 横浜(9) 34.0分

各駅の直前の駅
神田(1) <-- 東京(0)
上野(2) <-- 神田(1)
日暮里(3) <-- 上野(2)
池袋(4) <-- 新宿(7)
渋谷(5) <-- 新宿(7)
品川(6) <-- 東京(0)
新宿(7) <-- 神田(1)
川崎(8) <-- 品川(6)
横浜(9) <-- 川崎(8)

駅での停車時間がない分だけ早い気もしますが、
まあ、妥当かなともおもえます。


横浜駅発

2:横浜駅からの最短時間(分)
横浜(9) --> 東京(0) 34.0分
横浜(9) --> 神田(1) 36.0分
横浜(9) --> 上野(2) 41.0分
横浜(9) --> 日暮里(3) 45.0分
横浜(9) --> 池袋(4) 51.0分
横浜(9) --> 渋谷(5) 39.0分
横浜(9) --> 品川(6) 26.0分
横浜(9) --> 新宿(7) 45.0分
横浜(9) --> 川崎(8) 12.0分
横浜(9) --> 横浜(9) 0.0分

各駅の直前の駅
東京(0) <-- 品川(6)
神田(1) <-- 東京(0)
上野(2) <-- 神田(1)
日暮里(3) <-- 上野(2)
池袋(4) <-- 新宿(7)
渋谷(5) <-- 品川(6)
品川(6) <-- 川崎(8)
新宿(7) <-- 渋谷(5)
川崎(8) <-- 横浜(9)

こんなところでしょうか。



感想

こういうことはめんどくさいせいか?グラフ理論を開設するWebページではやっていません。
まあ、当然かな。
でも、品川-横浜間の京浜急行だったら?とか、新宿-横浜間の湘南新宿ラインは
どうなの?これだといろいろイメージがわきます。
おもしろいですね。


関連



参考



写真出典

「都会を走る山手線 E235系」 photoAC掲載 ちゃんこちゃんこさんの写真

#python
#経路探索
関連記事
スポンサーサイト



コメント

非公開コメント