摘要：由于是從頂點到的最短路徑，則有。算法流程根據最短路徑的最優子結構性質，提出了以最短路徑長度遞增，逐次生成最短路徑的算法。相關文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之三背包王者編程大賽之四約瑟夫環

首發于 樊浩柏科學院

自如年底就會擁有 50W 間房子，大家知道每間房房子都是需要配置完才能出租給自如客的，整個房租的配置過程是很復雜的，每天都需要大量的物流師傅將家電、家具等物品從倉庫送到需要配置的每個房間。

為了能在更多的時間配置更多的房子，我要不斷的優化物流從倉庫 A 到房間 G 的路徑或者倉庫 B 到房間 E 的距離，請寫出一種算法給你任意圖中兩點，計算出兩點之間的最短距離。
注：A B C D E F G H 都可能是倉庫或者房間，點與點之間是距離。

解題思路

該題是求解無向圖單源點的最短路徑，經常采用 Dijkstra 算法求解，是按路徑長度遞增的次序產生最短路徑。

算法理論

Dijkstra 算法是運用了最短路徑的最優子結構性質，最優子結構性質描述為：P(i,j) = {$v_i$,...,$v_k$,...,$v_s$,$v_j$} 是從頂點 i 到 j 的最短路徑，頂點 k 和 s 是這條路徑上的一個中間頂點，那么 P(k,s) 必定也是從 k 到 s 的最短路徑。

由于 P(i,j) = {$v_i$,...,$v_k$,...,$v_s$,$v_j$} 是從頂點 i 到 j 的最短路徑，則有 P(i,j) = P(i,k) + P(k,s) + P(k,j)。若 P(k,s) 不是從頂點 k 到 s 的最短路徑，那么必定存在另一條從頂點 k 到 s 的最短路徑 P"(k,s)，故 P"(i,j) = P(i,k) + P"(k,s) + P(k,j) < P(i,j)，與題目相矛盾，因此 P(k,s) 是從頂點 k 到 s 的最短路徑。

算法流程

根據最短路徑的最優子結構性質，Dijkstra 提出了以最短路徑長度遞增，逐次生成最短路徑的算法。譬如對于源頂點 $v_0$，首先選擇其直接相鄰的頂點中最短路徑的頂點$v_i$，那么可得從 $v_0$ 到達 $v_j$ 頂點的最短距離 $D[j]=min(D[j], D[j] + matrix[i][j])$（$matrix[i][j]$ 為從頂點 $v_i$ 到 $v_j$ 的直接距離）。

假設存在圖 G={V,E}，V 為所有頂點集合，源頂點為 $v_0$，U={$v_0$} 表示求得終點路徑的集合，D[i] 為頂點 $v_0$ 到 $v_i$ 的最短距離，P[i] 為頂點 $v_0$ 到 $v_i$ 最短路徑上的頂點。

算法描述為：

1）從 V-U 中選擇使 D[i] 值最小的頂點 $v_i$，將 $v_i$ 加入到 U 中；
2）更新 $v_i$ 與任一頂點 $v_j$ 的最短距離，即 $D[j]=min(D[j], D[i]+matrix[i][j])$；
3）直到 U=V，便求得從頂點 $v_0$ 到圖中任一一點的最短路徑；

例如，求 CG 最短路徑，算法過程可圖示為：

源頂點 $v_0$ = C，頂點與索引關系為 A→H = 0→7，初始時：

U = {false, false, false, false, false, false, false, false}

D = {INF ,INF, 0, INF, INF, INF, INF, INF}

P = { {}, {}, {C}, {}, {}, {}, {}, {} }

將頂點 C 包含至 U 中：

U = {false, false, true, false, false, false, false, false}

更新頂點 C 至任一節點的距離：

D = {6, 9, 0, 11, INF, INF, INF, INF}

P = { {C,A}, {C,B}, {C}, {C,D}, {}, {}, {}, {} }

再選擇不在 U 中的最短路徑頂點 A，則將 A 包含至 U 中：

U = {true, false, true, false, false, false, false, false}

更新頂點 A 至任一節點的距離：

D = {6, 9, 0, 11, INF, 25, INF, INF}

P = { {C,A}, {C,B}, {C}, {C,D}, {}, {C,A,F}, {}, {} }

繼續選擇不在 U 中的最短路徑頂點 B，則將 B 包含至 U 中：

U = {true, true, true, false, false, false, false, false}

更新頂點 B 至任一節點的距離：

D = {6, 9, 0, 11, 16, 25, INF, INF}

P = { {C,A}, {C,B}, {C}, {C,D}, {C,B,E}, {C,A,F}, {}, {} }

以此類推，直到遍歷結束：

U = {true, true, true, true, true, true, true, true}

D = {6, 9, 0, 11, 16, 21, 33, 16}

P = { {C,A}, {C,B}, {C}, {C,D}, {C,B,E}, {C,B,E,F}, {C,B,E,F,G}, {C,D,H} }

因此，CG 的最短距離為 33，最短路徑為 C-B-E-F-G。

編碼實現

實現的類結構如下，特殊的方法已提取出，并將一一詳細說明。

define("MAX", 9999999999);

class Path
{
    //圖對應索引數組
    public $indexMatrix = array();
    //頂點與索引映射關系
    public $indexMap = array();
    public $startPoint;
    public $endPoint;
    public $len = 0;
    //最短距離
    public $D = array();
    //已尋找集合
    public $U = array();
    //最短路徑
    public $P = array();

    public function __construct(array $matrix, $startPoint, $endPoint)
    {
        $this->indexMap = array_keys($matrix);
        $this->len = count($matrix);

        array_walk($matrix, function(&$value) {
            $value = array_values($value);
        });
        $this->indexMatrix = array_values($matrix);
        $this->startPoint = array_search($startPoint, $this->indexMap);
        $this->endPoint = array_search($endPoint, $this->indexMap);
        
        $this->init();
    }

    public function init()
    {
        for ($i = 0; $i < $this->len; $i++) {
            //初始化距離
            $this->D[$i] = $this->indexMatrix[$this->startPoint][$i] > 0 ? $this->indexMatrix[$this->startPoint][$i] : MAX;
            $this->P[$i] = array();
            //初始化已尋找集合
            if ($i != $this->startPoint) {
                array_push($this->P[$i], $i);
                $this->U[$i] = false;
            } else {
                $this->U[$i] = true;
            }
        }
    }
    
    public function getDistance()
    {
        return $this->D[$this->endPoint];
    }

    public function getPath()
    {
        $path = $this->P[$this->endPoint];
        array_unshift($path, $this->startPoint);

        foreach ($path as &$value) {
            $value = $this->indexMap[$value];
        }

        return $path;
    }
}

Dijkstra 算法求解：

public function dijkstra()
{
    for ($l = 1; $l < $this->len; $l++) {
        $min = MAX;
        //查找距離源點最近的節點{v}
        $v = $this->startPoint;
        for ($i = 0; $i < $this->len; $i++) {
            if (!$this->U[$i] && $this->D[$i] < $min) {
                $min = $this->D[$i];
                $v = $i;
            }
        }
        $this->U[$v] = true;

        //更新最短路徑
        for ($i = 0; $i < $this->len; $i++) {
            if (!$this->U[$i] && ($min + $this->indexMatrix[$v][$i] < $this->D[$i])) {
                $this->D[$i] = $min + $this->indexMatrix[$v][$i];
                $this->P[$i] = array_merge($this->P[$v], array($i));
            }
        }
    }
}

接收標準輸入處理并輸出結果：

//圖
$matrix = array(
    "A" => array("A" => MAX, "B" => 15, "C" => 6, "D" => MAX, "E" => MAX, "F" => 25, "G" => MAX, "H" => MAX),
    "B" => array("A" => 15, "B" => MAX, "C" => 9, "D" => MAX, "E" => 7, "F" => MAX, "G" => MAX, "H" => MAX),
    "C" => array("A" => MAX, "B" => 9, "C" => MAX, "D" => 11, "E" => MAX, "F" => MAX, "G" => MAX, "H" => MAX),
    "D" => array("A" => MAX, "B" => MAX, "C" => 11, "D" => MAX, "E" => 12, "F" => MAX, "G" => MAX, "H" => 5),
    "E" => array("A" => MAX, "B" => 7, "C" => 6, "D" => 12, "E" => MAX, "F" => 5, "G" => MAX, "H" => 7),
    "F" => array("A" => 25, "B" => MAX, "C" => 6, "D" => MAX, "E" => 5, "F" => MAX, "G" => 12, "H" => MAX),
    "G" => array("A" => MAX, "B" => MAX, "C" => MAX, "D" => MAX, "E" => MAX, "F" => 12, "G" => MAX, "H" => 17),
    "H" => array("A" => MAX, "B" => MAX, "C" => MAX, "D" => 5, "E" => 7, "F" => 25, "G" => 17, "H" => MAX),
);

//CG
while(!$input = trim(fgets(STDIN), "