乗り換え案内のためのグラフ構造
電車に関する知識が薄すぎてトンチンカンなことを言っている自信がある。何か間違いに気付いた電車オタクの人がもしいたら、連絡してください
↑の記事では、単純に駅（のグループ）をノード、駅間の隣接情報をエッジとしたグラフを作ってダイクストラで探索している（それで十分だから）
しかし、現実の乗り換えはそんなに単純ではない。考慮すべき事項が多くある
実例とともに考えよう
https://gyazo.com/705f671016714ee6bbf37866d16e74b5
これはヤフー。ここにある情報を出すには、どうすればいいか？を考える
急行
駅と駅の隣接ではなく、「ある駅からある駅まで、電車を降りることなく移動可能」をエッジにすることで解決しそう
これにより、たとえば中央線で東京から甲府に行きたいみたいな際、いっかい八王子で降りる必要がある、みたいなケースも解決可能
こういうのなんていうんだ？区間？
全ての列車について行うのではなく、急行だけ停車駅についてエッジを張るのはどうか？
https://gyazo.com/733e862749e39a5cdef9ee7e6ce5c21e
エッジの数値は所要時間として（時刻表みたいな面倒な概念はとりあえず無視）
これをうまく探索するアルゴリズムはパッと思いつかないな……
たとえば、立川→武蔵小金井 のルートについて
所要時間が最短のルートを探したいとする
これは単純に時間をコストにしてダイクストラすればいい
乗り換え回数が最小のルートは？
エッジに「各駅停車」とか「急行」みたいなラベルをつけておきつつ、探索時にコストを動的に計算する
現在のパスまでは各駅停車で来ていたとき、各駅停車のエッジの重みを 0, 急行の重みを 1 にする
vice versa
だるそう、、、
運賃が最小のルートは？
そもそも電車の運賃がどのように計算されるのか？について何の知識もないからわからない。
優先順位
乗り換えが少ない順
エッジを↑の持ちかたにした上で、幅優先探索
運賃が安い順
エッジに運賃を持たせて、コストをそれにしてダイクストラ
時間が短い順
エッジに時間を持たせて、コストをそれにしてダイクストラ
徒歩距離が短い順
エッジに徒歩距離を持たせて、コストをそれにしてダイクストラ
電車移動のエッジは0にする
N番線・同駅内徒歩
これは、「○○駅のN番線ホーム」をグラフのノードとして持つことで解決しそう
電車は、駅と駅ではなく、駅のホームと駅のホームの間を行き来するものとする
ホーム間の移動も同じく持てる
乗車位置
これよくわかってないんだけど階段が近いみたいなこと…？
時刻
そのホームからの全ての発車時刻について、「hh 時 mm 分における、○○駅の N 番線ホーム」をグラフのノードとして持つ？？？？
たとえば「10:15 分の上野駅2番線ホーム」というノード A から
「10:20 分の上野駅3番線ホーム」というノード B と
「10:25 分の上野駅3番線ホーム」というノード C
へはどちらにも到達可能であるべきだが、これについてどうエッジを張るべきか？？
A ==> B には 5 分のコストを持つエッジを、
A ==> C には 10 分のコストを持つエッジをつなぐ？
同じ駅（同じホーム）で待つ際も、過去から未来に向かう方向にエッジを張る
https://gyazo.com/2b45c483dbe66a8dafd9eee6b321a34a
↑これ全ての駅の全ての時刻表でやるのか？デカすぎる……
あとこれ 7 のエッジは不要じゃないか？7のエッジに相当する動作は以下の2択だから…
飯田橋で5分待って 11:07 の便で九段下に行く
11:04 の便で九段下に行って九段下で5分待つ
データ構造を工夫して単純なアルゴリズムで探索できるようにする v.s. アルゴリズムを工夫して単純なデータ構造で探索できるようにする の トレードオフ になっている気がする 休日ダイヤはどう扱う？
休日・平日でもう丸ごと違うグラフを使うのが手取り早いのでは
では、超長時間の移動で、平日→休日を跨ぐ必要性があるケースでは…？
エッジに休日フラグを持たせる…？
かなり巨大なグラフになってしまうのでは？
まあダイクストラをちゃんと O(nlogn) で実装しさえすればそこまで……？
ノード数・エッジ数を見積もろう
同一ホーム内の移動エッジだけで O(そのホームを発車する電車の本数 ^ 2) 個あるのか…
さすがに厳しいのでは
ひとつの路線に、駅が s 個あり、1日に t 本の電車が走るものとして
ノード数は st くらい
エッジ数は…？
少なくとも O(s^2 * t^2) みたいなオーダーになってくる気がする、、、
〇〇駅の〇番線で 15 時間待つ、みたいな異常なエッジを省いてもいい気はするけど
こういう恣意性を入れたくはないですよね
実際のデータで試してみたいだが、どこも有料だな…………