乗換案内をPythonで作ろう！最短経路探索アルゴリズムのUI実装

楽天モバイルならスマホの料金が超お得！
日本最大級ショッピングサイト！お買い物なら楽天市場

[トレード口座開設はコチラ↓]

みなさんこんにちは。ときか姉です♪

最近、早稲田大学・早水桃子先生の「離散数学入門#5最短経路問題」解説動画を拝聴しました。

それがとてもわかりやすく素敵な講義だったので、動画内で挙げられていた例題の最短経路問題を解く簡易版乗換案内を作ってみました。

早水先生の講義では、解法の一つであるダイクストラ法がひじょ〜にわかりやすく解説されています。

逆茂木がない見事な構成やリマインドのタイミングが絶妙でこういう素晴らしい解説にはとても憧れます。

講義の中で、東京-小田原間の最短経路探索を例題として扱われていました。

今回は、その例題に対してダイクストラ法を用いた最短経路探索を行う以下のようなアプリを作成します。

最短経路探索と描画を行うのものですが、除外する駅をラジオボタンで選択するとリアルタイムで再探索＆再描画を行うものです（図1, 2）。

以下に順を追って解説します。

コードの完全版のみ見たいor欲しいという方は文末をご参照ください♪

リンク

ライブラリのインポートと必要なデータの準備
Radio Buttonの配置
ダイクストラ法を用いた最短経路探索
ネットワーク図の描画
完全版コード（コピペで動きます）

ライブラリのインポートと必要なデータの準備

今回もUI設計にはstreamlitを用います。

streamlitは便利ですが、深いところにはなかなか触れなかったので私も最近webアプリ開発用に別の言語の勉強もしていました。

今回の実装もインタラクティブなグラフ操作が入りますので、作り始めた当初はさすがに今回ばかりはstreamlitだけでは難しいかなとあきらめていましたがなんとかなりました。

そのかいあって（？）未経験言語の習得は一向に進まずなんだかpython以外を回避する技術だけがどんどん上がっていってるような気がします。汗

扱うデータとしては、ノードである駅の名称リストとそのインデックス、描画のための駅座標の配列、エッジである駅間重み（所要時間などのコスト）の行列が必要となりますので以下のように定義しておきます。

# -*- coding: utf-8 -*-
import streamlit as st
import streamlit.components.v1 as components
import numpy as np
import networkx as nx
from pyvis.network import Network

st.title('ダイクストラ法のデモ') # タイトル

stations=['東京','品川','渋谷','新宿','新横浜','横浜','小田原'] # 駅名のリスト
sidx=list(range(len(stations))) # 駅名のインデックス
pos=list([[-4,0],[-1,0],[0,2],[-1,-2],[2,0],[3,-2],[5,0]]) # 描画のための駅の座標
# 駅間の所要時間の行列
w=[[ 0, 8,16,15, 0, 0, 0],
  [ 8, 0,13,21,10,17, 0],
  [16,13, 0, 0,27, 0,78],
  [15,21, 0, 0, 0,33, 0],
  [ 0,10,27, 0, 0,13,15],
  [ 0,17, 0,33,13, 0,52],
  [ 0, 0,78, 0,15,52, 0],
  ]

[Streamlitをもっと学ぶなら↓]

リンク

Radio Buttonの配置

今回はUIとしてRadioButtonを使用します。st.radioで定義できます。このradioで選択された駅を上記のリストから削除する操作が以下のように続きます。

# Radio buttonに用いる文字列
stlist=stations[1:-1] #Startの東京,Goalの小田原以外
stlist.append('除外しない') # '除外しない'を追加
removed_station=st.radio('除外する駅名',stlist) # Streamlitのradioを配置
# 選択されたitemのindex取得
idx=[i for i,s in enumerate(stations) if s==removed_station] 

# 条件に基づいた除外処理
if not idx: # '除外外しない'の場合
   pass
else: # 選択された駅をリストから削除
   idx=idx[0]
   stations.pop(idx) # 駅名リストから削除
   sidx.pop(idx) # 駅名インデックスから削除
   pos.pop(idx) # 駅座標から削除
   pos=np.array(pos) # 後のスライシングのためにnp.arrayにしておく
   # 結合行列から削除
   for i in range(len(w)):
       w[i].pop(idx)
   w.pop(idx)

[トレード口座開設はコチラ↓]

ダイクストラ法を用いた最短経路探索

ダイクストラ法の箇所ですが、今回は車輪の再発明はせずにnetworkxの関数を用います。

networkxの形式としてGraphオブジェクトを作成します。関数dijkstra_path, dijkstra_path_lengthを用いて最短経路とその合計コストをそれぞれ求めます。

G =nx.Graph() # 新規のNetworkxオブジェクト
for i in range(len(stations)):
   for j in range(len(stations)):
       if w[i][j]>0:
           G.add_edge(i,j,weight=w[i][j])

start_idx=[i for i,s in enumerate(stations) if s=='東京'][0]
goal_idx=[i for i,s in enumerate(stations) if s=='小田原'][0]

# Dijkstra法を適用（networkxのライブラリ）
path=nx.dijkstra_path(G,start_idx,goal_idx) # 最短経路の探索
length=nx.dijkstra_path_length(G,start_idx,goal_idx) # 最短経路のコスト計算

ネットワーク図の描画

描画のために、上で求めた最短経路の部分グラフを駅ペアのリスト化します。

また、求まった合計コストを表示します。

# 上で求めた最短経路を駅ペアのリストとして取得（描画のため）
path_pairs=list()
for i in range(len(path)-1):
   path_pairs.append([path[i],path[i+1]])

st.title(r'東京→小田原駅の最短経路')
'最短経路の合計コストは'+str(length)

ネットワーク描画には、pyvisのNetworkオブジェクトを用います。

ノード（駅）とエッジ（路線）をNetworkオブジェクトに追加します。最短経路内のパスは太い赤線で描画するようにします。

# Networkオブジェクトの用意
nt=Network("500px","700px",heading='')
# ノードを追加
for i in range(len(stations)):
   nt.add_node(i,label=stations[i],x=int(pos[i][0]*55),y=int(pos[i][1]*60))
# 以下で、nodeの物理効果をオフにする。
# オンのままだとある駅を動かすとnode間相互作用で他も動いてしまう
for n in nt.nodes:
   n.update({'physics':False})

# エッジを追加
for pair in G.edges:
   p=list(pair)
   col,wid=('red',10) if p in path_pairs else ('green',1) # 最短経路内のペアのみ太赤線にする
   nt.add_edge(p[0],p[1],color=col,width=wid,label=w[p[0]][p[1]]) # エッジの描画

Netwrokオブジェクトをhtmlファイルとして出力しstreamlitのcomponentに渡します。

# htmlファイルとして出力＆表示
nt.show('test.html')
htmlfile=open('test.html','r',encoding='utf-8')
source=htmlfile.read()
components.html(source,height=800,width=900)

リンク

完全版コード（コピペで動きます）

コードの完全版を以下に記します。

# -*- coding: utf-8 -*-
import streamlit as st
import streamlit.components.v1 as components
import numpy as np
import networkx as nx
from pyvis.network import Network

st.title('ダイクストラ法のデモ') # タイトル

stations=['東京','品川','渋谷','新宿','新横浜','横浜','小田原'] # 駅名のリスト
sidx=list(range(len(stations))) # 駅名のインデックス
pos=list([[-4,0],[-1,0],[0,2],[-1,-2],[2,0],[3,-2],[5,0]]) # 描画のための駅の座標
# 駅間の所要時間の行列
w=[[ 0, 8,16,15, 0, 0, 0],
  [ 8, 0,13,21,10,17, 0],
  [16,13, 0, 0,27, 0,78],
  [15,21, 0, 0, 0,33, 0],
  [ 0,10,27, 0, 0,13,15],
  [ 0,17, 0,33,13, 0,52],
  [ 0, 0,78, 0,15,52, 0],
  ]

# Radio buttonに用いる文字列
stlist=stations[1:-1] #Startの東京,Goalの小田原以外
stlist.append('除外しない') # '除外しない'を追加
removed_station=st.radio('除外する駅名',stlist) # Streamlitのradioを配置
idx=[i for i,s in enumerate(stations) if s==removed_station] # 選択されたitemのindex取得
if not idx: # '除外外しない'の場合
   pass
else: # 選択された駅をリストから削除
   idx=idx[0]
   stations.pop(idx) # 駅名リストから削除
   sidx.pop(idx) # 駅名インデックスから削除
   pos.pop(idx) # 駅座標から削除
   pos=np.array(pos) # 後のスライシングのためにnp.arrayにしておく
   # 結合行列から削除
   for i in range(len(w)):
       w[i].pop(idx)
   w.pop(idx)

G =nx.Graph() # 新規のNetworkxオブジェクト
for i in range(len(stations)):
   for j in range(len(stations)):
       if w[i][j]>0:
           G.add_edge(i,j,weight=w[i][j])

start_idx=[i for i,s in enumerate(stations) if s=='東京'][0]
goal_idx=[i for i,s in enumerate(stations) if s=='小田原'][0]

# Dijkstra法を適用（networkxのライブラリ）
path=nx.dijkstra_path(G,start_idx,goal_idx) # 最短経路の探索
length=nx.dijkstra_path_length(G,start_idx,goal_idx) # 最短経路のコスト計算

# 上で求めた最短経路を駅ペアのリストとして取得（描画のため）
path_pairs=list()
for i in range(len(path)-1):
   path_pairs.append([path[i],path[i+1]])

st.title(r'東京→小田原駅の最短経路')
'最短経路の合計コストは'+str(length)

# Networkオブジェクトの用意
nt=Network("500px","700px",heading='')
# ノードを追加
for i in range(len(stations)):
   nt.add_node(i,label=stations[i],x=int(pos[i][0]*55),y=int(pos[i][1]*60))
# 以下で、nodeの物理効果をオフにする。
# オンのままだとある駅を動かすとnode間相互作用で他も動いてしまう
for n in nt.nodes:
   n.update({'physics':False})

# エッジを追加
for pair in G.edges:
   p=list(pair)
   col,wid=('red',10) if p in path_pairs else ('green',1) # 最短経路内のペアのみ太赤線にする
   nt.add_edge(p[0],p[1],color=col,width=wid,label=w[p[0]][p[1]]) # エッジの描画

# htmlファイルとして出力＆表示
nt.show('test.html')
htmlfile=open('test.html','r',encoding='utf-8')
source=htmlfile.read()
components.html(source,height=800,width=900)

以上です。実行は以下のようにします。