Dijkstra vs貝爾曼福爾德定向圖，它會給出不同的結果

我想學習圖中，我發現找到從一個節點到其他節點的最短路徑，我們可以使用Dijkstra和Bellman-ford算法。Dijkstra vs貝爾曼福爾德定向圖，它會給出不同的結果

其中Dijkstra不適用於包含負加權邊的圖。雖然Brllman-ford可以處理這種包含負重量邊緣的Graph。

我的疑問是我嘗試了許多種圖形，其中包含負重量邊緣和應用Dijkstra和Bellman福特都但在所有情況下，我發現相同的結果我的意思沒有區別，負重邊緣也dijkstra工作正常。可能是我的思維過程或我如何解決問題的方式是錯誤的，所以只有我得到了dikstra的正確答案。

我的問題是，任何人都可以解釋一個負面的邊緣圖，並解釋dijkstra和bellman-ford的不同結果。

2014-09-25 Amit Kumar

如果源頂點則u採取u到v成本5，U爲w成本6，和W到V作爲成本-2。 – 2014-09-25 16:58:29

是的，迪傑克斯特拉可以給出錯誤的答案。看到一個美麗的例子http://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm。 – axiom 2014-09-25 16:58:37

找到兩條邊之間最短路徑的Djikstra算法只能用於具有正權重的圖。看到答案的差異，當有一個下降沿重量貝爾曼 - 福特和djikstra給人，讓我們來簡單的例子

we have 3 nodes in the graph, A B C 
A is connected to B edge weight 4 
A is connected to C edge weight 2 
B is connected to C edge weight -3

時djikstra用於計算A和C之間的最短路徑，我們得到的重量2

但當貝爾曼 - 福特被用來計算A和C之間的最短路徑，所述權重爲1

這是因爲，djikstra定型具有最小邊的權重的節點，忽略了以下事實發生事實上，可能有一個路徑的權重較小的節點（注意，這可能會發生只有當負面重量是存在的。只有正面權重是不可能的）。

希望你理解差異

2014-09-25 16:55:49 Haris

我們是否將訪問過的節點信息保存在某個地方。在我的情況下，我喜歡爲您告知的圖：A - > B和A - > c權重爲2和4.因此，我的優先級隊列是「CB」那麼我會刪除C.但是當我將處理B時，我會知道我可以用-1的成本到達C，所以更新我的隊列的距離 – 2014-09-25 17:01:01

@AmitKumar：不完全確定你在問什麼。 bellman-ford算法在整個過程中永遠不會移除任何頂點，而在djikstra每次迭代中，權重最小的頂點都會被完成並添加到最短路徑。 – Haris 2014-09-25 17:06:59

@AmitKumar：你不會在djikstra那樣做。一旦選定的路徑（A - > C）沒有改變。 – Haris 2014-09-25 17:08:47

回答