[請問] 演算法問題Minimum cost graph DAG

[tzuchun42 (TzuChun)]

大家好，抱歉我找不到一個版是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
推 Schottky: 九宮格的狀況，cost 是在 vertices 上而非 edge 上
→ tzuchun42: 對 是在vertex上 我舉例只是舉個2*2的想說這樣應該就夠
→ tzuchun42: 了  _
→ Schottky: 所以你不應該轉成差值啊
→ Schottky: 「你從五樓爬到四樓為什麼要那麼久」「幹，不同棟啊」
推 jatj: Dynamic Programming
推 lubu: 假設11 3 2分別為 v0,v1,v2 graph 就是v1-v0+v2-v1=v2-v0,
→ lubu: 而另一個是v0+v1+v2 是不同的