Dijkstra最短路徑算法[貪心]

Dijkstra算法的标記和結構與prim算法的用法十分相似。它們兩者都會從餘下頂點的優先隊列中選擇下一個頂點來構造一顆擴充樹。但千萬不要把它們混淆了。它們解決的是不同的問題，是以，所操作的優先級也是以不同的方式計算的：Dijkstra算法比較路徑的長度，是以必須把邊的權重相加，而prim算法則直接比較給定的權重。

源最短路徑問題

給定一個帶權有向圖 G=(V,E) ，其中每條邊的權是一個非負實數。另外，還給定 V 中的一個頂點，稱為源。現在我們要計算從源到所有其他各頂點的最短路徑長度。這裡的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。

這裡模仿MST(Minimum Spanning Tree)的Prim算法，我們建立一個SPT(最短路徑樹)，最初隻包含源點。我們維護兩個集合，一組已經包含在SPT(最短路徑樹)中的頂點S集合,另一組是未包含在SPT内的頂點T集合。每次從T集合中選擇到S集合路徑最短的那個點，并加入到集合S中，并把這個點從集合T删除。直到T集合為空為止。

舉例說明，如下圖所示的圖：

S集合最初為空，然後選取源點0，S集合為 {0}，源點到其它所有點的距離為 {0, 4, INF, INF, INF, INF, 8, INF} 。圖中藍色表示 SPT，疊代的過程如下

最終得到 SPT(最短路徑樹) 如下：

算法C++實作：

我們使用Boolean 數組sptSet[] (也有習慣用visit[]命名，表示是否通路過)，來表示頂點是否為有SPT中。sptSet[v]=true,說明頂點v在SPT中。 dist[] 用來存儲源點到其它所有點的最短路徑。

運作結果如下：輸出源點0到其它各個頂點的最短距離：