#はじめに
取り組んだ研修があまりにも骨太だったので備忘録として残しておきたく、書くことにしました。
#お題のルール
この問題は以下の条件を元に取り組んでいます。
- モデルは京急線全域とする（73駅）。
路線図（公式サイト） - ダイヤは考慮しない。
- 一駅につき普通列車は5分かかるものとする。なおエアポート急行は4分、特急は3分、快特は2分、エアポート快特は1分それぞれかかるものとする。
- 停車時間は1分とし、乗換は停車時間中に行えるものとする。
- 出発駅と到着駅を選択し、最短経路と所要時間を表示する。ただし乗り換えずに通過した駅は表示しないものとする。
- 逆走は禁止。
#ヒント
1.京急線は枝分かれがいくつか存在している。分岐の基準になる駅（羽田空港行きの枝の場合は京急蒲田駅）を境目とし、路線に番号を付ける。分岐の駅は接続する全ての番号が対応するものとする。
2.開始駅と到着駅がどの路線に属しているのかを調べ、その路線を一本になるように繋げる。その為に一本道になるルートをあらかじめ洗い出しテーブルで検索できるようにしておく。例えば[1,2]（泉岳寺〜羽田空港）、[1,3,5,6]、[2,3,4]などが該当し、計15ルートある。
3.ルートに該当する全ての駅情報を抽出し、順番通りに並び替える。ルートによっては枝分かれの駅順が逆になるケースがあるのでひっくり返す。
4.３のデータをもとに最短経路を求める。
#今回の方針
最短経路問題自体初めてだったので、調べたらよく出てきた「ダイクストラ法」という総当たりで解く公式を採用しました。
この方式を使うには、隣り合う駅の時間を記した隣接行列が必要とのことでした。
ということで方針は以下のようにしました。
1.止まる電車と所属する路線idを持った駅テーブルを作る。
2.一本道になるルートをカンマで区切ったルートテーブルを作る。
3.駅テーブル~ルートテーブル間の中間テーブルを作り、ルートに応じた駅情報を抽出できるようにする。
４.ビューを作り、1~3のテーブルをphp内のSQLを駆使し必要なデータを抽出する、順番が逆になる駅があればUnionでひっくり返したものを引っ付ける。
5.駅情報を元に到着する電車の種類に応じで時間を振った配列を作成する。
6.5によってできたものをまとめて隣接行列とし、ダイクストラ法に代入する。
7.表示したい情報を出す為、参考にしたダイクストラ法のコードを加工する。
8.完成！
やった感想としては、隣接行列を作成することと、ダイクストラ法を理解し加工することがこの問題の肝だなと感じました。
次回はDBから必要なデータをを抽出するパートです。コードを書きながら解説しようと思います。
SQL編に続く
#参考サイト
ダイクストラ法（最短経路問題）
PHPでダイクストラ法