最大流最小費用演算法中的spfa找增廣路是貪心演算法嗎？

《ACM國際大學生程序設計競賽 演算法與實現》書中2.5.5 費用流 中的演算法中使用spfa找增廣路然後增廣。spfa的距離指標是費用。我用這個模板改寫了符合自己要求的程序，但是結果不對，找到的不是最優解，是我用錯演算法了嗎？

---

• 首先反正是你錯了。
• 其次在這裡SPFA的意義是代替EK演算法裡面的BFS的功能(這個BFS又是為了代替FF裡面DFS的功能)，具體是什麼你自己想想。
• 最後其他人到底在回答什麼我完全沒看懂。

---

@Coldwings在他的回答的評論里有句話說得很好

動態規劃和貪心本就是思路而其實稱不上演算法。

你硬要往定義上套的話，貪心的意思就是你在當前狀態下直接找個指標來評價你的所有選項的好壞。講道理，沒人能阻止你把「我dp/枚舉了所有情況然後把算出來的玩意作為指標，然後把這個演算法稱作貪心」。

但是沒什麼用，這樣做唯一的效果是讓你自己的表達能力變得匱乏，因為詞都被你玩壞了。

所以，最小費用最大流的那個演算法每次求最短路來增廣到底算不算貪心……你開心就好……

當然， @Coldwings 他的回答本身審題錯了……於是其實不太相關……這個……請去看 @Adder 的回答……

至於為什麼你的程序運行結果錯了……你需要做的是

1. 找出一個反例，然後通過手畫，驗證這個演算法確實錯了。或者
2. 找出一個反例，然後通過手畫，發現你的程序的輸出跟演算法應當給出的輸出不同，從而說明你的演算法錯了。

由於你的程序已經掛了，上面的1和2顯然至少有一個為真。你需要做的是找反例，分析到底是1這個情況還是2這個情況。當然，我們這裡所有人應該都相信是2（逃

---

謝邀！

原來隊友搞過最大流和學習運籌學的時候學過！題主問的不是貪心演算法，而是動態規劃！

---

不是貪心

是你用錯了

spfa是單源最短路演算法，其實質與dijkstra一致，理論原理都是動態規劃的最優子結構與無後效性，找增廣路是單源最短路問題，沒毛病。

所以，要麼你寫錯，要麼構圖錯，要麼理解有誤，可以從中選一樣來描述你的問題。

---

寫個我博客中的通俗易懂的理解吧

所謂最小費用最大流：就是在保證從源點 S 到匯點 T 的流量最大的前提下，使費用最小

這就在原先最大流問題的網路中，給每條邊上新加上了費用，求的不在是最大流，而是在最大流的前提的下最小費用，最大流的路可能有多條。

求解最大流的時候，我們不斷的在殘餘網路上不斷的貪心增廣而得到最大流，現在邊上多了費用，而求得正好是最小的費用，那麼我們是不是每次可以沿著最短路增廣呢，每條邊的費用看作是權值，這樣求得的必然是最小費用最大流。

至於寫錯了，先找個模板研究研究，研究懂了自己寫一個自己的模板，網路流難點在於建圖，建圖好了就剩套模板的事情了。

---

推薦閱讀：