2016/12/7 Algorithm (Bellman-Ford & Dijkstra's Algorithm)

Ch24.3 Bellman–Ford algorithm
參考: 
https://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%9B%BC-%E7%A6%8F%E7%89%B9%E7%AE%97%E6%B3%95

它的原理是對圖進行V-1次鬆弛操作，得到所有可能的最短路徑。其優於Dijkstra's Algorithm的方面是邊的權值可以為負數、實作簡單，缺點是時間複雜度過高，高達${\displaystyle O(VE)}$。

以鬆弛操作為基礎，估計的最短路徑值漸漸地被更加準確的值替代，直至得到最優解。
在兩個演算法中，計算時每個邊之間的估計距離值都比真實值大，並且被新找到路徑的最小長度替代。 

然而，Dijkstra's演算法以Greedy策略選取未被處理的具有最小權值的節點，然後對其的出邊進行鬆弛操作；而Bellman–Ford 演算法簡單地對所有邊進行鬆弛操作，共|V | − 1次，其中 |V |是圖的點的數量。在重複地計算中，已計算得到正確的距離的邊的數量不斷增加，直到所有邊都計算得到了正確的路徑。這樣的策略使得Bellman–Ford 演算法比Dijkstra's演算法適用於更多種類的輸入。

Ch24.3 Dijkstra's Algorithm
參考: 

• http://www.csie.ntnu.edu.tw/~u91029/Path.html#4
• https://zh.wikipedia.org/wiki/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95

已知起始點, 由起始點慢慢長出最小生成樹
這個演算法是通過為每個頂點 v 保留目前為止所找到的從s到v的最短路徑來工作的。
對於不含負權的有向圖，這是目前已知的最快的單源最短路徑演算法。

演算法維護兩個頂點集合 S 和 Q。集合 S 保留所有已知最小 d[v] 值的頂點 v ，而集合 Q 則保留其他所有頂點。集合S初始狀態為空，而後每一步都有一個頂點從 Q 移動到 S。這個被選擇的頂點是 Q 中擁有最小的 d[u] 值的頂點。當一個頂點 u 從 Q 中轉移到了 S 中，演算法對 u 的每條外接邊 (u, v) 進行拓展。