PHP
アルゴリズム

PHPでダイクストラ法

More than 3 years have passed since last update.


PHPでダイクストラ法


ダイクストラ法とは

グラフ上の2頂点間の最短経路を効率的に求めるアルゴリズム

スタート地点から近いノードから順番に最短経路を求め、最終結果を出す


問題

プログラミングの宝箱 アルゴリズムとデータ構造 第2版のダイクストラ法の問題

各経路の最短時間を求めよ

各駅の所要時間は隣接行列の$adjacencyMatrixを参照する事。

横浜→横浜

横浜→武蔵小杉

横浜→品川

横浜→渋谷

横浜→新橋

横浜→溜池山王


コード

define('STATION_NUMBER',6);

define('START_STATION', 0);

$stations = array('横浜', '武蔵小杉', '品川', '渋谷', '新橋', '溜池山王');

//隣接行列
//各所要時間を保持する
$adjacencyMatrix = array(
//横浜', '武蔵小杉', '品川', '渋谷', '新橋', '溜池山王'
array(0, 12, 28, 0, 0, 0), //横浜基準
array(12, 0, 10, 13, 0, 0), //武蔵小杉基準
array(28, 10, 0, 11, 7, 0), //品川基準
array(0, 13, 11, 0, 0, 9), //渋谷基準
array(0, 0, 7, 0, 0, 4), //新橋基準
array(0, 0, 0, 9, 4, 0) //溜池山王
);

for ($i=0; $i < STATION_NUMBER; $i++) {
$currentCost[$i] = -1; //-1は無限大とする
$fix[$i] = false;
}

//スタート地点を0とする
$currentCost[START_STATION] = 0;

while (true) {
//所要時間を無限大に初期設定する
$minStation = -1;
$minTime = -1;
for ($i = 0; $i < STATION_NUMBER; $i++) {
if (!$fix[$i] && ($currentCost[$i] != -1)) {
if ($minTime == -1 || $minTime > $currentCost[$i]) {
//パターン洗い出しが終わってなく、所要時間の短い駅を調べる
$minTime = $currentCost[$i];
$minStation = $i;
}
}
}
if ($minTime == -1) {
//全ての駅が確定したか、最初の所要時間が無限大のとき
break;
}

// 自分の駅から伸びているすべての駅の所要時間を調べる
for ($i = 0; $i < STATION_NUMBER; $i++) {
if (!$fix[$i] && $adjacencyMatrix[$minStation][$i] > 0) {
// 自分の駅経由で移動する場合の必要時間
$newTime = $minTime + $adjacencyMatrix[$minStation][$i];
if ($currentCost[$i] == -1 || $currentCost[$i] > $newTime) {
// 今登録されている時間よりも、この駅経由で移動した時間が速いので、新しい時間を登録する
$currentCost[$i] = $newTime;
}
}
}
// 自分の駅を確定する
$fix[$minStation] = true;
}
for ($i = 0; $i < STATION_NUMBER; $i++) {
echo ($stations[START_STATION] . "→" . $stations[$i] . ":" . $currentCost[$i] . "分");
echo '<br>';
}


参考書籍

プログラミングの宝箱 アルゴリズムとデータ構造 第2版


参考サイト

http://www.sousakuba.com/Programming/algo_root.html

http://tech.nitoyon.com/ja/blog/2010/01/26/dijkstra-aster-visualize/