1樓：乙隻菜雞
我覺得是這樣的問題，導致他不能計算負權重,如果我們是這樣計算的，S->V的權值為3，S->W的權值為2，然後S被標記訪問過，接著重點來了，S->W->？，但是W到不了其他節點，則W被標記訪問過，那麼S->V->W應該為1，因為W已經被訪問過了就無法計算了。
2樓：Lin Jack
簡單但可能需要仔細琢磨的回答：
我們能那麼自信的在鬆弛後選最近的點A晉級（「鬆弛並選最近點」，加入已確定最短路徑的點的集合，我稱之為「晉級」），不就是因為如果選稍遠一點的點B晉級，之後B再來鬆弛A也只能使A比當前A更遠而不能更近了嘛？為啥？因B到A為正權邊，B無法再縮短A的距離。
故都為正權邊時，這點自信是該有的。
但若B到A是負權邊，則B還真能鬆弛A以讓A比當前更近，故現在就晉級A當然就不對了。這就是Dijkstra不對的情況。
也就是說，當圖中存在負權邊的情況時，必有某一步晉級某點時，漏考慮了將來可能突然出現的黑馬負邊，以致當前這步晉級是非最優的（即此點如果別那麼早晉級，再被鬆弛一下其實還能更短）。
3樓：xiaobo tang
你這個按照Dijkstra的演算法，我保證你是算不出來d(w)=1的，你的演算法實現肯定有一些小問題。按照下面這個Dijkstra的步驟我給你解析一下下：
step 1: S= ; Q = ;
step 2：S = ; Q = ;
step 3: S = ; Q = {};
Dijkstra 結束！！！
樓主注意，這是乙個directed graph，不是乙個undirected graph!!!!! 從w是不能update v的！！！
從上面的這個分析可以總結出：樓主的Dijkstra的實現過程有瑕疵。據我推測樓主實現的是general structure for shortest path （就是講每乙個vertex的edges都relax一下，而不是dijkstra）, 二者是不一樣滴。
4樓：marcelyz
不能，因為Dijkstra's algorithm這樣假設：對於處理過的節點，沒有前往該節點的更短路徑。這種假設僅在沒有負權邊時才成立。
因此，不能將Dijkstra's algorithm用於包含負權邊的圖。
在包含負權邊的圖中，要找出最短路徑，可以使用另一種演算法：Bellman–Ford algorithm。
5樓：魯沛瑤
你計算出正確的答案是因為你在最後一次計算出d(v) = 2;之後對d又進行了一次更新。計算出了d(w)=1。
事實上算出來d(w)=1【只能證明】這個演算法【應用】到【負權邊】的圖里是【錯的】。
因為Dijkstra演算法的思路是貪心（先算出從原點出發第一短的d(w) = 2，再利用第一短的更新計算出第二短的d(v)=3
你這樣計算出來的結果通過第二短的路徑d(v)=3又計算出了第一短的路徑d(w)=1。已經與原始的思想出現了不一致。所以不能通過這個演算法計算帶有負權邊的圖。
當出現以下情況的時候就不會計算出正確的結果了。
圖中再新增兩個個節點x，y，w(w,x) = 0.5，w(x,y) = 0.2。
1）計算出第一短的邊s->w,d(w) = 2;更新d陣列
2）計算出第二短的邊s->w->x d(x) = 2.5;更新d陣列
3）計算出第三短的邊s->w->x->y d(y) = 2.7;更新d陣列
4）計算出第四短的邊s->v d(v) = 3;更新d陣列，乙個【已計算】出最短路徑的節點被更新，得到d(v) = 1;然而既然d(v)更新了，從原點經過v的路徑也應該更新如x->v->x 。然而事實上並沒有。
所以Dijkstra演算法的貪心策略並不能處理帶有負權邊的圖。
6樓：陸宇慶
dijkstra演算法正確的前提是長的路徑是由短的路徑派生而來的。但是一旦存在了負的權值，那麼乙個最短路徑就可能在增加這個負權值的路線後變成更短的路徑。也就是說含有負的權值的圖是不能保證dijkstra演算法存在的正確前提的，那麼dijkstra演算法也就無從成立了。
我的理解是雖然這個圖用dijkstra求出來的路徑是符合的。但是他的前提是錯誤的，即初始的時候演算法認為S到所有點中的最短路徑長就是S->W是等於2的，那麼一旦把W加入被訪問後點集合，這條S->W的路徑你就是不能再更改的了，再進行後續計算的時候這個值也是不能變化的！但是實際上我們都能看出來如果考慮上負邊，那麼S到W的最短路徑不是S->W而是S->V->W了！
但是又因為W加入了被訪問後點集合，那麼S->W是不能被更新的。所以完蛋了！
一句話：只有當所有權都為非負的時候，你才能在和S連通的所有點中找出可以確定下來的最短的路。
也就是說連前提都已經是錯的了，那麼結果是對的也不能說明你這個方法是正確的，因為他沒有普適性。
7樓：Alvin Fan
你按標準的Dijkstra演算法走一遍就知道了，算不出d(w)=1的。
第一步，從優先佇列裡取下點w,因為邊sw是從s能到達的定點中權值最小的。於是sw在此之後就不會再被更新了。
8樓：馬睿沙
1.Dijkstra演算法是用來解決non-negative-weight的最短路程問題的。本就不應該企圖用Dijkstra來解決這個問題。
2. Dijkstra解決你的例子沒得到錯誤答案只是巧合，不能保證在其他有負權重時依然得解。
3.如果負權重沒有鏈結到目標點，Dijkstra一定會得到錯誤，因為會在起點和目標點之間產生loop(不斷走負權重來縮短路徑）。如果只有一條負權重並通向終點，Dijkstra才可以用來正確地解決這個問題（就像你的例子）。
最短路徑問題，面試官說BFS和Bi BFS都太費空間，問如果空間不夠該怎麼辦？
程式小猿 V代表頂點數量，E代表邊的數量。用BFS解決單源最短路徑問題，空間是和V成正比的，時間和EV成正比。樓下的回答提到了Bellman Ford演算法，基於佇列的這個版本演算法，就是利用的BFS，在這個過程中relax節點。樸素的Bellman Ford會以任意順序relax。它們在最壞的情況...
用鄰接表建圖，解決一下最短路徑？
林濯 Dijkstra用一句話概括就是 每一次從所有點中找出距源點的距離已經無法更新的最近的點，以這個點為中間點，更新源點到其它可更新的點的距離。做N 1遍 N為點數 就做完了。比方說上圖，先把廣州丟到乙個坑里，這個坑叫做 已經最短不能再短坑 初始除了深圳和株洲這兩個與廣州直接相連的點，其他點到廣州...
空間曲面上兩點之間最短路徑怎麼求
土星的熊貓 首先考慮變分法，即對任一已知L xi，xi t 對映為一標量s時 s a b Ldt 可以使s取到極值的xi xi t 的函式形式。於是，先考慮於三維空間中無約束的情況，有 即三維空間中無約束下直線為長度極值 最短 其中x x y y z z t 4個自由度由3個函式關係表徵，3個約束方...