ダイクストラアルゴリズム 単一始点最短経路 Single Source Shortest Path : PHPで実装

Tweet

Pocket

重み付きグラグの最短経路を求めるダイクストラアルゴリズムのサンプルです。

<?php
<?php
/*
 * 単一始点最短経路 Single Source Shortest Path
 * 
 * ダイクストラ アルゴリズム Dijkstra Algorithm 
 * 
 * 頂点0(始点)から各頂点への最短距離を求めます。
 * 頂点0から各頂点へ必ず経路があることを前提としています。
 */
class DKA
{
    /** @var integer $n 頂点数 */
    private $n;
    /** @var integer $matrix 隣接行列 */
    private $matrix;
    /** @var  integer[] $distance 最短距離 */
    private $distance = [];
    /** @var boolean[] $visited 訪問済みフラグ */
    private $visited = [];
    /** @var integer[] $parents 親頂点 */
    private $parents = [];
    /** @var integer[] $path 経路 */
    private $path = [];
    /** @var integer $time 時刻 */

    /**
     * DKA constructor.
     *
     * @param integer   $n      頂点数
     * @param integer[] $matrix 隣接行列 m[i][j]はiからjへの辺の重み。辺がないときはINF。
     */
    function __construct($n, array $matrix)
    {
        $this->n        = $n;
        $this->matrix   = $matrix;
        $this->distance = array_fill(0, $n, INF);
        $this->visited  = array_fill(0, $n, false);
    }

    /**
     * 最短経路計算
     */
    public function search()
    {
        $this->distance[0] = 0;
        $this->parents[0]  = -1;
        $this->time        = 0;
        while (true) {
            $min = INF;
            $u   = INF;
            /**
             * 距離が最小かつ未到達頂点へ移動
             */
            for ($i = 0; $i < $this->n; $i++) {
                if (!$this->visited[$i] && $this->distance[$i] < $min) {
                    $min = $this->distance[$i];
                    $u   = $i;
                }
            }
            if (is_infinite($min)) {
                break;
            }
            $this->visited[$u]       = true;
            $this->path[$this->time] = $u;
            $this->time += 1;
            /**
             * 次回遷移候補を選択するため距離再計算
             * 未到達かつ距離の既存より小さいときは距離更新
             */
            for ($v = 0; $v < $this->n; $v++) {
                if (!$this->visited[$v] && !is_infinite($this->matrix[$u][$v])) {
                    if ($this->distance[$v] > $this->distance[$u] + $this->matrix[$u][$v]) {
                        $this->distance[$v] = $this->distance[$u] + $this->matrix[$u][$v];
                        $this->parents[$v]  = $u;
                    }
                }
            }
            if (!in_array(false, $this->visited)) {
                break;
            }
        }
    }

    /**
     * 距離取得
     *
     * @return integer[] 始点からの距離の配列
     */
    public function getDistance()
    {
        return $this->distance;
    }

    /**
     * @return integer[] 親を記録した配列
     */
    public function getParents()
    {
        return $this->parents;
    }

    /**
     * 経路取得
     *
     * @return integer[]
     */
    public function getPath()
    {
        return $this->path;
    }
}