1樓：
關於這個負值圈的講解比較少，所以大致說一下。下文以D演算法代稱Dijkstra演算法。
因為正數是越加越大的，所以在一條鏈上的資料一定會是遞增的（就算考慮上零權，任何一條鏈也不會在某處減小）。在這個前提下才能建立起之前所說的這個D演算法，也就是說，某個節點在進入queue再彈出之後，就找出了它的最小值，這一點不會隨著鏈節的延長而改變。有了這樣的前提，D演算法就可以放心大膽地在標記這個位置以後再也不用管它，一旦訪問到了直接退出，不做修改就是了。
STOP，在這裡要做乙個辨析。和處理負權圖的演算法一樣，D演算法中也有找到了更短的路線而改變距離的環節，但是D演算法的改變和這裡的改變是不同的：在D演算法中，只有本輪中被放在隊首的節點才能被彈出，彈出之前才能被標記為已經訪問過（這裡的訪問與記憶化搜尋中的已訪問概念不同，這裡指的是已經結束了最小值的判斷，以後不會再改變了，其實換稱為「已確認」會更好一點）。
再說回到負權圖。因為負權會導致遞增鏈的前提條件被推翻，不能簡單的認為前面的一定比後面小，所以「已確認」的概念就不成立了，每次由乙個節點指向其他的節點，不過曾經有沒有訪問過，都必須要重新判斷——到底是記錄裡的路程短呢？還是繞道所得到的這個路程短呢？
在每一次發現被指向點時都要進行判斷，沒有「已確認」這個概念，如同不進行記憶化搜尋的遞迴問題，這也就是MAW所指出的「the cost of a drastic increase in running time」。
下面附上MAW 資料結構與演算法分析C語言描述原文（有一說一，翻譯的真不咋地，中英文對照著看吧。）
2樓：Sails
若是無向圖，a<->b 權值為負，Dijkstra演算法到達a或b後會進入死迴圈：a->b->a->b->a->b->a->b->a->b->.......
3樓：張揚
Dijkstra不能解決有負權的圖。原因在於Dijkstra的貪心演算法的本質是如下條件要成立：
如果存在某條路徑p,使得p是從頂點u到v的最短路徑：p = u->v1->v2...->vn->v,則對於任意的1<=k<=n,需要滿足 d(u,vk)c （正確解應該是a->b->c）
4樓：
受邀……
乙個沒有環的無向圖就是樹，這樣的圖里兩點之間有唯一的路徑，就不用找最短的了……
Dijkstra和Bellman-Ford的區別是前者過於貪心，負權的情況他不考慮，也無能力考慮。
後者反覆調整，保證精確，順便可以探知無解的情況。
把握了對 科研 的話語權是不是生化環材專業最大的惡
我可以說不止生化環材四大天坑專業，幾乎所有專業的所謂科研人員都在水文章騙錢好不好？全是禍害。只是生化環材專業的學生招生太多，業界已經飽和，更加苦命。 mengy 哪一行都有泡沫，材料科學目前是佔據了大量的學術資源，但學術圈本身就不聖潔，教授們也不都勵志當要傳奇科學家，大多數人都是通過乙份專長混一口飯...
想問一下，環藝考研的話快題手繪如果平時用iPad練手會不會對後期考研時直接手繪有影響呢？
設計小黃人 用ipad手繪的開始也行，可以提公升對自己色彩的理解，但一定要有乙個過渡期去練習動手能力，畢竟考研考的不是用電腦畫 手法什麼的也要多練練 愛問知識人 這個當然會有影響的，之前我乙個同學也是經常用iPad練手繪，每次他正式考試的時候，手繪的很慢並且最後手繪出來的作品很不理想。最後老師和他分...
男朋友沒有承諾的話，是不是可以分手了？
奔跑的小張老師 題主，我真的很想吐槽你。都老大不小了，竟然還和20歲小姑娘一樣，要個承諾？別要個什麼承諾了，白紙黑字法律保護的才是有用的。誰都可以說的比唱的好聽，你不要糾結他給不給你承諾，你要糾結的是你們倆的問題，他有沒有實質性的做出付出和盡可能的去解決。不要用耳朵去聽愛情！ 情況是剛剛公升職了，剛...