#あらすじ
最初のパートはこちら
隣接行列編で出発駅と到着駅の隣接行列を作成した。
#今回の目的
ダイクストラ法に隣接行列を代入し、最短経路を表示させる。
#ダイクストラ法とは
スタートノードからゴールノードまでの最短距離とその経路を求めることができる、最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。簡潔に言うと経路を総当たりで探す力技です。
説明するとすごく長くなるので、まずは参考資料をご覧ください。
ダイクストラ法（最短経路問題）
PHPでダイクストラ法
ダイクストラ法の手順としては開始地点からいける地点に移動しつつ、地点毎のコストを加算していき、計算し終わった地点にフラグを立て戻れなくすることで全経路のコストを算出すると言うことです、全地点のコストを算出できるので２番目の参考資料の様に表示させることもできます。
２番のダイクストラ法の作り方を採用したのですが、当然問題点もあります。
1.全経路ではなく、到着駅の経路だけ表示させたい。
2.途中駅の情報を保持できず、開始駅⇨到着駅の情報しか表示することができない。
この二つを解決できるように改良する必要があります。
#ダイクストラ法を使ってみよう
ではダイクストラ法書いていきましょう。
define('STATION_NUMBER',count($bigarray));
define('START_STATION', $start);
define('GOAL_STATION', $goal);
$stations = $station_names;
$routes = [];
$result = [];
//隣接行列
//各所要時間を保持する
$adjacencyMatrix = $bigarray;
$adjacencyMatrix2 = $bigarray2;
//1.初期設定する
for ($i=0; $i < STATION_NUMBER; $i++) {
$currentCost[$i] = -1; //-1は無限大とする
$fix[$i] = false; //trueにするとその駅を再度通れなくなる
}
//2.スタート地点を-1→0とする（スタートノード）
$currentCost[START_STATION] = 0;
$test = array();
while (true) {
//3.所要時間を無限大に初期設定する
$minStation = -1;
$minTime = -1;
//
for ($i = 0; $i < STATION_NUMBER; $i++) {
//4.もし[$fix[$i]がfalse]かつ[$currentCost[$i]が-1でない]なら(初めはスタートノード、以降は次の駅)
if (!$fix[$i] && ($currentCost[$i] != -1)) {
//5.もし[$minTimeが∞]か[$minTimeが$currentCost[$i]よりおおきい]なら
// $minTime == -1はスタートノードで０が代入
if ($minTime == -1 || $minTime > $currentCost[$i]) {
//パターン洗い出しが終わってなく、所要時間の短い駅を調べる
//6.(ここで下のFor分に使う変数を代入する。)
$minTime = $currentCost[$i];
$minStation = $i;
}
}
}
if ($minTime == -1) {
//全ての駅が確定したか、最初の所要時間が無限大のとき
break;
}
// 自分の駅から伸びているすべての駅の所要時間を調べる
for ($i = 0; $i < STATION_NUMBER; $i++) {
//もし[$fix[$i]がfalse]かつ[$minStation番目の駅情報が０より大きい]とき
if (!$fix[$i] && $adjacencyMatrix[$minStation][$i] > 0) {
// 自分の駅経由で移動する場合の必要時間
$newTime = $minTime + $adjacencyMatrix[$minStation][$i];
// 今登録されている時間よりも、この駅経由で移動した時間が速い時、新しい時間を登録する
if ($currentCost[$i] == -1 || $currentCost[$i] > $newTime) {
$train = $adjacencyMatrix2[$minStation][$i];
$currentCost[$i] = $newTime;
if(!isset($test[$i])){
$test[$i] = array();
}
//途中経路を表示
$test[$i][] = array($train,$stations[$i]);
if(isset($test[$minStation])){
$test[$i] = array_merge($test[$minStation],$test[$i]);
}
}
}
}
// 自分の駅を確定する
$fix[$minStation] = true;
}
はいややこしい！はじめわけわからなすぎてコメントいっぱいですがご了承ください。
では順に解説していきます。
まず隣接行列編で作ったデータを代入していきます。
define('STATION_NUMBER',count($bigarray));
define('START_STATION', $start);
define('GOAL_STATION', $goal);
$stations = $station_names;
$routes = [];
$result = [];
//隣接行列
//各所要時間を保持する
$adjacencyMatrix = $bigarray;
$adjacencyMatrix2 = $bigarray2;
次に初期設定をしておきます。まだ通っていない駅は-1で、後戻り禁止のフラグは全部falseにしておきます。その後開始駅だけ0にしておきます。
//1.初期設定する
for ($i=0; $i < STATION_NUMBER; $i++) {
$currentCost[$i] = -1; //-1は無限大とする
$fix[$i] = false; //trueにするとその駅を再度通れなくなる
}
//2.スタート地点を-1→0とする（スタートノード）
$currentCost[START_STATION] = 0;
$test = array();
次に計算する際の基準駅を探します。開始駅は０にしているのでこれが基準になります。次回以降は他の駅の−１がコストに変わっているのでそれが基準になります。ここで駅のidとかかったコストを保存し、次の計算に使います。
もし該当する駅がなければbreakで終了します。
while (true) {
//3.所要時間を無限大に初期設定する
$minStation = -1;
$minTime = -1;
//
for ($i = 0; $i < STATION_NUMBER; $i++) {
//4.もし[$fix[$i]がfalse]かつ[$currentCost[$i]が-1でない]なら(初めはスタートノード、以降は次の駅)
if (!$fix[$i] && ($currentCost[$i] != -1)) {
//5.もし[$minTimeが∞]か[$minTimeが$currentCost[$i]よりおおきい]なら
// $minTime == -1はスタートノードで０が代入
if ($minTime == -1 || $minTime > $currentCost[$i]) {
//パターン洗い出しが終わってなく、所要時間の短い駅を調べる
//6.(ここで下のFor分に使う変数を代入する。)
$minTime = $currentCost[$i];
$minStation = $i;
}
}
}
if ($minTime == -1) {
//全ての駅が確定したか、最初の所要時間が無限大のとき
break;
}
//続く
ここで上から取ってきた情報から、次の駅のコストを計算していきます。もし複数同じ駅に止まるルートがあるなら最短のものが記されます。このタイミングで駅の経路情報を配列でどこから、なんの電車に乗ったか記録しておきます。計算が終わったら後戻り禁止のフラグを立てます。
// 自分の駅から伸びているすべての駅の所要時間を調べる
for ($i = 0; $i < STATION_NUMBER; $i++) {
//もし[$fix[$i]がfalse]かつ[$minStation番目の駅情報が０より大きい]とき
if (!$fix[$i] && $adjacencyMatrix[$minStation][$i] > 0) {
// 自分の駅経由で移動する場合の必要時間（到達駅までのコストを足してる）
$newTime = $minTime + $adjacencyMatrix[$minStation][$i];
// 今登録されている時間よりも、この駅経由で移動した時間が速い時、新しい時間を登録する
if ($currentCost[$i] == -1 || $currentCost[$i] > $newTime) {
$train = $adjacencyMatrix2[$minStation][$i];
$currentCost[$i] = $newTime;
//途中経路を記録
if(!isset($test[$i])){
$test[$i] = array();
}
$test[$i][] = array($train,$stations[$i]);
if(isset($test[$minStation])){
$test[$i] = array_merge($test[$minStation],$test[$i]);
}
}
}
}
// 自分の駅を確定する
$fix[$minStation] = true;
}
#最短経路を表示しよう
この時点で駅毎の所要時間は出てきました。ただし最短になる経路はどの電車に乗ればいいのかも必要ですね。それを表示できるように記録した配列を加工していきましょう。
$savetrain;
$getroutes =[];
foreach($test[GOAL_STATION] as $route){
// スタートの隣がゴールなら
if (count($test[GOAL_STATION]) === 1){
array_push($getroutes,$route);
}elseif ($route === reset($test[GOAL_STATION])) {
// 最初
$savetrain = $route;
}else if ($savetrain[0] === $route[0] && $route === end($test[GOAL_STATION])) {
// 最後
array_push($getroutes,$route);
}else{
if($savetrain[0] === $route[0]){
$savetrain = $route;
}else{
array_push($getroutes,$savetrain);
// 最後
if ($route === end($test[GOAL_STATION])) {
array_push($getroutes,$route);
}
}
$savetrain = $route;
}
}
$text = "";
foreach($getroutes as $getroute){
$text .= "-(" . $getroute[0] . ")-" . $getroute[1];
}
$result = $stations[START_STATION] . $text . "[所要時間" . ($currentCost[GOAL_STATION] - 1) . "分]";
echo json_encode($result);
exit;
ここでは経路に使った経路に必要な情報を抽出しています。例えば特急で二駅通った時、特急が二つ並ぶ情報ははじめに出る情報としては不要なので省きます。ただ開始駅の隣が到着駅のケース等もあるのでそれを考慮した結果複雑になっています。
最後に厳選した配列を使い出力用に加工していけば・・・
はいドン！結果が出力できるようになりました！このダイクストラ法は迷路とかでも利用できるので、興味あれば試していただけたらと思います。
#最後に
４パートに渡って最短経路問題について書いてきましたが、いや本当に長い・・。普段使われてる駅探などのアプリはこの規模の比じゃないことを考えると、鉄道会社のノウハウとデータの蓄積は尋常じゃないんだろうなと感じてしまいます。ただこれが人に見せるものに仕上げることができただけでも自信がついたのは事実なので、この小さな自信を積み重ねていこうと思います。
#参考サイト
ダイクストラ法（最短経路問題）
PHPでダイクストラ法