為什麼這篇graph演算法鄉民發文收入到精華區：因為在graph演算法這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者tzuchun42 (TzuChun)看板ask標題[請問] 演算法問題Minimum cost...
大家好，抱歉我找不到一個版是algorithm的
請問minimum cost problem跟換成graph是一樣的嗎
Minimumcost來想是：
譬如我有一個九宮格起點左上終點右下九宮格裡面有數字，我要找其中一條路徑使得總和最小（只能左上右下）
Graph的話，有點像shortest path, 但是edge 可以是negative weighted(因為是差）
同個九宮格但是不是算點，把點跟點的差變成邊，求解最短路徑。
這兩個問題是一樣的嗎？
其實我有找到一個可能是證明不一樣的
11 3
-5 2
左上到右下graph解起來兩種走法分別是-9 -9 兩條都是最短路徑
但是minimum cost解起來就分別是16 8
這樣下L走法就是最小成本
但我不確定隨便找個例子來證明是否可以。
求解QQ
-----
Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 175.97.16.202
※ 文章網址: https://www.ptt.cc/bbs/ask/M.1543511729.A.E52.html
→ Ricestone: Prob_Solve 11/30 02:47
推 Schottky: 九宮格的狀況，cost 是在 vertices 上而非 edge 上 11/30 02:53
→ tzuchun42: 對 是在vertex上 我舉例只是舉個2*2的想說這樣應該就夠 11/30 07:15
→ tzuchun42: 了 _ 11/30 07:15
→ Schottky: 所以你不應該轉成差值啊 11/30 16:13
→ Schottky: 「你從五樓爬到四樓為什麼要那麼久」「幹，不同棟啊」 11/30 16:14
推 jatj: Dynamic Programming 12/01 04:29
推 lubu: 假設11 3 2分別為 v0,v1,v2 graph 就是v1-v0+v2-v1=v2-v0, 12/01 14:25
→ lubu: 而另一個是v0+v1+v2 是不同的 12/01 14:25