Dijkstra不能得到含有負權邊圖的單源最短路徑

Dijkstra算法當中将節點分為已求得最短路徑的集合（記為S）和未确定最短路徑的個集合（記為U），歸入S集合的節點的最短路徑及其長度不再變更，如果邊上的權值允許為負值，那麼有可能出現當與S内某點（記為a）以負邊相連的點（記為b）确定其最短路徑時，它的最短路徑長度加上這條負邊的權值結果小于a原先确定的最短路徑長度，而此時a在Dijkstra算法下是無法更新的，由此便可能得不到正确的結果。求帶負權值邊的單源最短路徑可以用貝爾曼-福特算法

。

原文連結：

http://www.cnblogs.com/tanhehe/archive/2013/02/03/2890767.html