昨天復習了一下單源最短路徑問題，今天總結一下。

解決單源最短路徑問題，我們熟知的算法首先就是Dijkstra算法了。Dijkstra算法的核心就是貪心思想。我在以前的博客中也寫過這個算法：圖的拓撲排序、關鍵路徑、最短路徑算法 – C++實現，現在看以前的博客，我的代碼思路還是很清晰的。Dijkstra算法可以求出某一點到其他所有點的最短路徑，本文還將介紹一種可求出所有點對的最短路徑的算法——Floyd算法。

Dijkstra算法

Dijkstra算法是典型的單源最短路徑算法，用于計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，知道擴展到終點為之。Dijkstra算法的要求是圖中不存在負權邊。因為Dijkstra算法基于貪心策略，它是短視的。如果存在某個路徑上有負權邊，可能繞了幾圈得到的結果甚至是更優的，所以Dijkstra算法在有負權邊的圖應用上是失敗的。

Dijkstra算法的具體解釋我就不說了，如果不明白概念可參考這篇博客的概念解釋：最短路徑—Dijkstra算法和Floyd算法。

本文所有測試用例所用graph就是下面這幅圖片中的graph：

下面給出我的代碼：

輸出結果：

Dijkstra算法的時間復雜度是O(|E|+|V|2|)=O(V2)$O(|E|+|V|^2|) = O(V^2)$（參考：Dijkstra算法時間復雜度）。對于稠密的圖來說，|E| 就是|V|^2，所以Dijsstra算法中遍歷dist[min_index]+weigth那個循環加上最外層循環時間復雜度為θ(|V|2)$θ(|V|^2)$，對于稠密圖，這就是最優的了，總的時間復雜度正好是θ(|E|+|V|2)=θ(|V|2+|V|2)=O(|V|2)$θ(|E|+|V|^2) = θ(|V|^2+|V|^2) = O(|V|^2)$。但是對于非稠密圖，這個 |E| 實際沒這么大，甚至 |E|=|V|$|E| = |V|$，這個算法就未免效率低下了。

優化法方法是使用最小堆，我們dist[min_Index]+weight小于dist[k]時，將新的dist[k]的值插入最小堆；在上面查找最小值的操作中，每次從最小堆中取出最小值，并且檢查是否visited，如果沒visited，那就找到新的頂點了。改進后的算法時間復雜度是O(|E|lg|V|)$O(|E|lg|V|)$。

Floyd算法

Floyd算法是解決任意兩點間最短路徑的一種算法，可以正確處理負權圖的最短路徑問題。

上面的Dijkstra算法求出了某個點到其他所有點的最短路徑，我們要求所有點對的最短路徑，有這樣一種思路，就是再外面再循環 |V| 次，那么不就求出所由點對的最短路徑了嗎？時間復雜度為O(N3)$O(N^3)$。

不過，Dijkstra算法為我們提供了一種動態規劃的思想，一個點到另外一個點的最短路徑，要么直接到達就是最短的，要么就是經過了一個已經最優化的點間接到達這個點就是最短的，只有這么兩種情況。Floyd算法就根據這個思路把所有情況同過DP表的方式計算出來，時間復雜度是一樣的，也是O(N3)$O(N^3)$，不過Floyd算法簡潔的多。

Floyd算法DP公式：

D0[V][W]=min{D?1[V][W],D?1[V][K]+D?1[K][W]} $$D^0[V][W]=min/{ D^-1[V][W], D^-1[V][K]+D^-1[K][W]/}$$

D是一個二維矩陣，是一個輔助矩陣，初始狀態和graph是一致的，通過該矩陣的變化，我們來修正path矩陣的值即可。

更多的關于Floyd算法的解釋參見： 數據結構之最短路徑（Floyd） ，包括我下面用的打印函數，可以參見它的解釋。不過它的打印函數對于非強連通圖有一點問題，我加以修正了。

打印函數實際上意思就是，比如我要找(0, 8)的最短路徑，如果path[0][8]的值為k，說明0->8之間經過路徑k，且0->k的結果是最優的，所以目前找到了所求路徑的一部分{0, k1}。然后我們再次查找(k, 8)的最短路徑，看它們兩之間有沒有中間更優化的路徑，比如找到，如果有，那就找到了路徑{0, k1, k2}，依次下去，知道path[k][8]的結果為8，說明沒有了?？偟穆窂骄褪莧0, k1, k2 … 8}。

下面給出我的代碼：

輸出結果：