LoginSignup
5
2

More than 3 years have passed since last update.

@PAmatsuti(アマツチ)

PHPで駅をモデルにした最短経路問題を解く(3/4 隣接行列編)

Last updated at Posted at 2019-05-18

あらすじ

最初のパートはこちら

SQL編で出発駅と到着駅のルート上の駅データを抽出した。

今回の目的

データを加工し、ダイクストラ法に使用するための隣接行列にする。

隣接行列とは

頂点と頂点の隣接関係を表わす正方行列です。
例えば四角に書かれた線があるとして、頂点をそれぞれA,B,C,Dとします。
各辺にはそれぞれコストが振られています。今回は所要時間で表現します。
A-B間は1分、BーC間は2分、C-D間は3分、D-A間が4分かかるとすると、隣接行列は以下のような二次元配列で表すことができます。

sample.php
$bigarray = array(
//----A,B,C,D
array(0,1,0,4),//A 
array(1,0,2,0),//B
array(0,2,0,3),//C
array(4,0,3,0) //D
);

０番目の配列はAから向かえる頂点と、そのコストを表しています。リーグ戦の表をイメージするといいかもしれませんね。０番目配列内の０番目はA自身なので０、１番目はBで1分、２番目はCで行けないから0,3番目はDで4分ということを示しています。
A-C間のコストを計算すると、A-Bの1分とB-Cの2分の計３分のルートと、A-Dの4分とD-Cの3分の計7分の二つのルートがあることがわかります。
ダイクストラ法はこの隣接行列を利用して最短経路を解いていくので、使用するデータは最終的にこの形まで持っていきます。

余計なデータを削ろう

早速データを隣接行列に加工したいところですが、実はこれだと提示された条件が達成されないことがあります。何かというと「逆走禁止」です。開始駅から手前に戻って早い電車に乗る、あるいはオーバーランして到着駅に戻るルートがあると逆走が発生するので、端っこの余分なデータは消しましょう。（ちなみに到着時間が同じルートがあると、現時点の仕様だとダブってしまいました。逆走まで考慮すると相当難しいから禁止にしたって意味が何となく分かりました。）

sample.php
            while($result = $stmt3->fetch(PDO::FETCH_ASSOC)){
                //DBのデータ
                $allstations[] = $result;
            }
            //余計なデータを削除
            if (isset($allstations)){
                $bigarray = [];
                $bigarray2 = [];
                $station_names = [];
                $i = 0;
                foreach($allstations as $station){
                    //出発駅
                    if ($_POST["d_station"] === $station["id"]){
                        $startstation = $i;
                    }
                    if ($_POST["a_station"] === $station["id"]){
                        $goalstation = $i;
                    }
                    $i++;
                }
                $arraystation = [];
                $i = 0;
                $j = 0;
                if($startstation < $goalstation ){
                    $start = 0;
                    foreach($allstations as $station){
                        if ($i >= $startstation && $i <= $goalstation ){
                            array_push($arraystation, $station);
                            $j++;
                        }
                        $i++;
                    }
                    $goal = $j -1;
                }else{
                    $goal = 0;
                    foreach($allstations as $station){
                        if ($i >= $goalstation && $i <= $startstation ){
                            array_push($arraystation, $station);
                            $j++;
                        }
                        $i++;
                    }
                    $start = $j -1;
                }
                $count = $j -1;
                $i = 0;

開始駅と到着駅の位置を確認し、端っこの駅情報を含めずに配列を作り直しています。そこまで難しいことはしていませんので詳細は割愛します。この場合だと仲木戸より下のデータは捨てています。

情報２.png

隣接配列を作ろう

ではお待たせしました、隣接配列を作っていきましょう。これも実はそこまで難しくないのですが、まとめてないものもあるので結構長いですよ？

index.php
                    array_push($station_names, $station["name"]);
                    $array = [];
                    $array2 = [];
                    //all0の配列を全体の配列に挿入する
                    for($j = 0; $j <= $count; $j++ ){
                        array_push($array, 0);
                        array_push($array2, 0);
                    }
                    array_push($bigarray, $array);
                    array_push($bigarray2, $array2);
                    if($i == 0){
                        // 初期値
                        // 普通
                        $local = $station["local"] ==1? 0: -1;
                        // エアポート急行
                        $a_express = $station["a_express"] ==1? 0: -1;
                        // 特急
                        $l_express = $station["l_express"] ==1? 0: -1;
                        // 快特
                        $kl_express = $station["kl_express"] ==1? 0: -1;
                        // エアポート快特
                        $ak_express = $station["ak_express"] ==1? 0: -1;
                    }else{
                        // コストを算出
                        // 普通
                        if ($station["local"] == 1 && $local !==-1 ){
                            $bigarray[$local][$i] = 6;
                            $bigarray[$i][$local] = 6;
                            $bigarray2[$local][$i] = "普通";
                            $bigarray2[$i][$local] = "普通";
                            $local =  $i;
                        }
                        // エアポート急行
                        if ($station["a_express"] == 1 && $a_express !==-1 ){
                            $bigarray[$a_express][$i] = 4 * ($i - $a_express) +1;
                            $bigarray[$i][$a_express] = 4 * ($i - $a_express) +1;
                            $bigarray2[$a_express][$i] = "急行";
                            $bigarray2[$i][$a_express] = "急行";
                            $a_express =  $i;
                        }
                        // 特急
                        if ($station["l_express"] == 1 && $l_express !==-1 ){
                            $bigarray[$l_express][$i] = 3 * ($i - $l_express) +1;
                            $bigarray[$i][$l_express] = 3 * ($i - $l_express) +1;
                            $bigarray2[$l_express][$i] = "特急";
                            $bigarray2[$i][$l_express] = "特急";

                            $l_express =  $i;
                        }
                        // 快特
                        if ($station["kl_express"] == 1 && $kl_express !==-1 ){
                            $bigarray[$kl_express][$i] = 2 * ($i - $kl_express) +1;
                            $bigarray[$i][$kl_express] = 2 * ($i - $kl_express) +1;
                            $bigarray2[$kl_express][$i] = "快特";
                            $bigarray2[$i][$kl_express] = "快特";
                            $kl_express =  $i;
                        }
                        // エアポート快特
                        if ($station["ak_express"] == 1 && $ak_express !==-1 ){
                            $bigarray[$ak_express][$i] = 1 * ($i - $ak_express) +1;
                            $bigarray[$i][$ak_express] = 1 * ($i - $ak_express) +1;
                            $bigarray2[$ak_express][$i] = "エアポート快特";
                            $bigarray2[$i][$ak_express] = "エアポート快特";
                            $ak_express =  $i;
                        }
                        // 使用できる電車が増えたら追加する
                        if ($local == -1 && $station["local"] ==1){
                            $local = $i;
                        }
                        if ($a_express == -1 && $station["a_express"] ==1){
                            $a_express = $i;
                        }
                        if ($l_express == -1 && $station["l_express"] ==1){
                            $l_express = $i;
                        }
                        if ($kl_express == -1 && $station["kl_express"] ==1){
                            $kl_express = $i;
                        }
                        if ($ak_express == -1 && $station["ak_express"] ==1){
                            $ak_express = $i;
                        }
                    }
                    $i++;
                }
index.php
    //all0の配列を全体の配列に挿入する
    for($j = 0; $j <= $count; $j++ ){
        array_push($array, 0);
        array_push($array2, 0);
    }
    array_push($bigarray, $array);
    array_push($bigarray2, $array2);

まずは隣接行列の枠を作ります。今は全部０にしていますが、所要時間が計算できれば上書きしていきます。

index.php
    if($i == 0){
        // 初期値
        // 普通
        $local = $station["local"] ==1? 0: -1;
        // エアポート急行
        $a_express = $station["a_express"] ==1? 0: -1;
        // 特急
        $l_express = $station["l_express"] ==1? 0: -1;
        // 快特
        $kl_express = $station["kl_express"] ==1? 0: -1;
        // エアポート快特
        $ak_express = $station["ak_express"] ==1? 0: -1;
    }else{
    // コスト算出
    }

開始駅から使用する電車にフラグを立てます。フラグの立った駅と電車を基準に次止まる駅の所要時間を計算します。止まらない電車は次回以降の駅で止まる駅が出てくるまで使いません。

index.php
    if($i == 0){
        // 初期値

    }else{
    // コスト算出
                        // 普通
                        if ($station["local"] == 1 && $local !==-1 ){
                            $bigarray[$local][$i] = 6;
                            $bigarray[$i][$local] = 6;
                            $bigarray2[$local][$i] = "普通";
                            $bigarray2[$i][$local] = "普通";
                            $local =  $i;
                        }
                        // エアポート急行
                        if ($station["a_express"] == 1 && $a_express !==-1 ){
                            $bigarray[$a_express][$i] = 4 * ($i - $a_express) +1;
                            $bigarray[$i][$a_express] = 4 * ($i - $a_express) +1;
                            $bigarray2[$a_express][$i] = "急行";
                            $bigarray2[$i][$a_express] = "急行";
                            $a_express =  $i;
                        }
                        // 特急
                        if ($station["l_express"] == 1 && $l_express !==-1 ){
                            $bigarray[$l_express][$i] = 3 * ($i - $l_express) +1;
                            $bigarray[$i][$l_express] = 3 * ($i - $l_express) +1;
                            $bigarray2[$l_express][$i] = "特急";
                            $bigarray2[$i][$l_express] = "特急";

                            $l_express =  $i;
                        }
                        // 快特
                        if ($station["kl_express"] == 1 && $kl_express !==-1 ){
                            $bigarray[$kl_express][$i] = 2 * ($i - $kl_express) +1;
                            $bigarray[$i][$kl_express] = 2 * ($i - $kl_express) +1;
                            $bigarray2[$kl_express][$i] = "快特";
                            $bigarray2[$i][$kl_express] = "快特";
                            $kl_express =  $i;
                        }
                        // エアポート快特
                        if ($station["ak_express"] == 1 && $ak_express !==-1 ){
                            $bigarray[$ak_express][$i] = 1 * ($i - $ak_express) +1;
                            $bigarray[$i][$ak_express] = 1 * ($i - $ak_express) +1;
                            $bigarray2[$ak_express][$i] = "エアポート快特";
                            $bigarray2[$i][$ak_express] = "エアポート快特";
                            $ak_express =  $i;
                        }
                        // 使用できる電車が増えたら追加する
                        if ($local == -1 && $station["local"] ==1){
                            $local = $i;
                        }
                        if ($a_express == -1 && $station["a_express"] ==1){
                            $a_express = $i;
                        }
                        if ($l_express == -1 && $station["l_express"] ==1){
                            $l_express = $i;
                        }
                        if ($kl_express == -1 && $station["kl_express"] ==1){
                            $kl_express = $i;
                        }
                        if ($ak_express == -1 && $station["ak_express"] ==1){
                            $ak_express = $i;
                        }
                    }
                    $i++;
                }

次回以降の駅で止まる電車の所要時間を計算し、配列に上書きしていきます。普通電車ならほぼ止まるので隣り合った駅に5分と停車時間1分の計6分を配列に入れます。もし泉岳寺⇨品川の様に止まる電車が複数ある場合は、早い電車に上書きされます。途中で特急等の電車が使える様になったらフラグを立て直して計算できる様にしておきます。

この処理を実行すると、下の様な隣接行列が出来上がります！
一番目が泉岳寺、最後が仲木戸ですね。
情報３.png

うーん大きい！当然通過する駅が多いほどこの行列も大きくなります。書き忘れていましたが、bigarray2にはどの電車を使用したかを記録しています。これは次回使用します。

さてこれで隣接行列が出来上がりました。次回はこれを使って最短経路を表示させて終了としましょう。
次回最終回！ダイクストラ法編に続く。

5
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
2