dijkstra演算法O(n2) 堆優化O（nlogn）

用來計算從一個點到其他所有點的最短路徑的演算法，是一種單源最短路徑演算法。也就是說，只能計算起點只有一個的情況。 Dijkstra的時間複雜度是O (N2)，它不能處理存在負邊權的情況。 演算法描述： 設起點為s，dis[v]表示從s到v的最短路徑，pre[v]為v的前驅節點，用來輸出路徑。 a)初始化：dis[v]=∞(v≠s); dis[s]=0; pre[s]=0; b)For (i = 1; i <= n ; i++) 1.在沒有被訪問過的點中找一個頂點u使得dis[u]是最小的。 2.u標記為已確定最短路徑 3.For 與u相連的每個未確定最短路徑的頂點v if (dis[u]+w[u][v] < dis[v]) { dis[v] = dis[u] + w[u][v]; pre[v] = u; } c)演算法結束：dis[v]為s到v的最短距離；pre[v]為v的前驅節點，用來輸出路徑。 演算法分析&思想講解： 從起點到一個點的最短路徑一定會經過至少一個「中轉點」（例如下圖1到5的最短路徑，中轉點是2。特殊地，我們認為起點1也是一個「中轉點」）。顯而易見，如果我們想求出起點到一個點的最短路徑，那我們必然要先求出中轉點的最短路徑（例如我們必須先求出點2 的最短路徑後，才能求出從起點到5的最短路徑）。 換句話說，如果起點1到某一點V0的最短路徑要經過中轉點Vi，那麼中轉點Vi一定是先於V0被確定了最短路徑的點。

演算法開始時，作為起點的dis[1] = 0，其他的點dis[i] = 0x7fffffff。

接下來的兩輪循環將4、5也變成白點。N輪循環結束後，所有的點的最短路徑即能求出。 Dijkstra無法處理邊權為負的情況，例如右圖這個例子。 2到3的邊權值為-4，顯然從起點1到3的最短路徑是-2（1→2→3），但是dijskstra在第二輪循環開始時會找到當前dis[i]最小的點3，並標記它為白點。 這時的dis[3]=1，然而1卻不是從起點到點3的最短路徑。因為3已被標記為白點，最短路徑值dis[3]不會再被修改了，所以我們在邊權存在負數的情況下得到了錯誤的答案！

next數組版+堆優化O(nlogn)

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！