位置ゲー攻略のためにPythonとNetworkXで最短経路を探る(1)

はじめに

当方、駅メモという鉄道の位置ゲーをずっと遊んでおり、かれこれ3000日以上ログインしています。
「駅メモ！」とは、全国9,000ヶ所以上ある駅を対象とした位置ゲームです。 個性的なパートナーキャラ「でんこ」と一緒に、 毎日の通勤・通学、おでかけを楽しんでみませんか？(駅メモwebサイトより)
ということで、GPSを使った駅巡りのスタンプラリーのようなゲームです。（バトル要素などもありますが）

https://youtu.be/bLcYK0vdsVk

現在、実装されている駅数は9366駅もあり、私は先日ついにアクセスした駅が9000駅を突破しました。

もうちょっとでコンプリートだ！！というわけでもなく・・・
これまでは行きたい旅行先に行くだけで駅が取れていましたが、今ではアクセスしにくい場所や盲腸線（終点が他の駅に接続していない路線）の駅が大量に残っています。これらの駅がなかなか取りづらく、コンプリートを難しくしています。

ということでITの力を借りて最短ルートでコンプリートを目指したいと考えました。

データ収集

【駅データ.jp】さんが無償で駅や路線のデータを公開してくれているのでこちらを使わせていただきます。

データは事業者データ、路線データ、駅データ、接続駅データの4種類があります。
それぞれの仕様についてはこちらを確認してください。
もしくはこちらにチラ見できるnotebookを置いたので確認してみてください。

経路探索

とりあえず実装案を膨らませるために動かしてみます。
横浜駅から鳥取駅までの経路を探させると

出力は・・・

最短経路（駅名）: 横浜 -> 川崎 -> 品川 -> 新橋 -> 東京

おお、いい感じですね。
では、まだ行ったことない鳥取では

経路が見つかりません。

あれ？

よく見ると

def get_station_cd(station_name):
    station_cd = stations.loc[stations["station_name"] == station_name, "station_cd"]
    if not station_cd.empty:
        return station_cd.iloc[0]
    else:
        raise ValueError(f"No station found with name {station_name}")

この関数でiloc[0]を指定しているのがダメですね。
また、同じ駅での乗り換えをエッジに追加するべきでした。

というわけで修正したものが

出力は・・・

最短経路（駅名）: 横浜 -> 戸塚 -> 大船 -> 藤沢 -> 辻堂 -> 茅ケ崎 -> 平塚 -> 大磯 ->
二宮 -> 国府津 -> 鴨宮 -> 小田原 -> 早川 -> 根府川 -> 真鶴 -> 湯河原 -> 熱海 ->
熱海 -> 函南 -> 三島 -> 沼津 -> 片浜 -> 原 -> 東田子の浦 -> 吉原 -> 富士 -> 富士川 ->
新蒲原 -> 蒲原 -> 由比 -> 興津 -> 清水 -> 草薙 -> 東静岡 -> 静岡 -> 安倍川 -> 用宗 ->
焼津 -> 西焼津 -> 藤枝 -> 六合 -> 島田 -> 金谷 -> 菊川 -> 掛川 -> 愛野 -> 袋井 ->
御厨 -> 磐田 -> 豊田町 -> 天竜川 -> 浜松 -> 浜松 -> 高塚 -> 舞阪 -> 弁天島 ->
新居町 -> 鷲津 -> 新所原 -> 二川 -> 豊橋 -> 西小坂井 -> 愛知御津 -> 三河大塚 ->
三河三谷 -> 蒲郡 -> 三河塩津 -> 三ケ根 -> 幸田 -> 相見 -> 岡崎 -> 西岡崎 -> 安城 ->
三河安城 -> 東刈谷 -> 野田新町 -> 刈谷 -> 逢妻 -> 大府 -> 共和 -> 南大高 -> 大高 ->
笠寺 -> 熱田 -> 金山 -> 尾頭橋 -> 名古屋 -> 枇杷島 -> 清洲 -> 稲沢 -> 尾張一宮 ->
木曽川 -> 岐阜 -> 岐阜 -> 西岐阜 -> 穂積 -> 大垣 -> 垂井 -> 関ケ原 -> 柏原 ->
近江長岡 -> 醒ケ井 -> 米原 -> 米原 -> 坂田 -> 田村 -> 長浜 -> 虎姫 -> 河毛 -> 高月 ->
木ノ本 -> 余呉 -> 近江塩津 -> 新疋田 -> 敦賀 -> 敦賀 -> 西敦賀 -> 粟野 -> 東美浜 ->
美浜 -> 気山 -> 三方 -> 藤井 -> 十村 -> 大鳥羽 -> 若狭有田 -> 上中 -> 新平野 ->
東小浜 -> 小浜 -> 勢浜 -> 加斗 -> 若狭本郷 -> 若狭和田 -> 若狭高浜 -> 三松 -> 青郷 ->
松尾寺 -> 東舞鶴 -> 東舞鶴 -> 西舞鶴 -> 真倉 -> 梅迫 -> 淵垣 -> 綾部 -> 綾部 ->
高津 -> 石原 -> 福知山 -> 上川口 -> 下夜久野 -> 上夜久野 -> 梁瀬 -> 和田山 -> 養父 ->
八鹿 -> 江原 -> 国府 -> 豊岡 -> 豊岡 -> 玄武洞 -> 城崎温泉 -> 竹野 -> 佐津 -> 柴山 ->
香住 -> 鎧 -> 餘部 -> 久谷 -> 浜坂 -> 諸寄 -> 居組 -> 東浜 -> 岩美 -> 大岩 -> 福部 -> 鳥取

出ました！
でもこれ各駅停車っぽいですね・・・18きっぷ旅ならこれでもいいですが・・・
次回は駅間の距離や時間なども考慮に入れて作成します。