作者tzuchun42 (TzuChun)
看板Prob_Solve
標題[問題] minimum cost problem & DAG graph short
時間Fri Nov 30 07:20:01 2018
大家好，抱歉我找不到一個版是algorithm的
請問minimum cost problem跟換成graph是一樣的嗎
Minimumcost來想是：
譬如我有一個九宮格起點左上終點右下九宮格裡面有數字，我要找其中一條路徑使得總和
最小（只能左上右下）cost在vertex
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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1543533604.A.218.html
1F：推 springman: 你的graph的做法長度是不是都是終點的值減起點的值，如 11/30 09:22
2F：→ springman: 您的例的長度是 2-11=-9，與中間經過哪些點無關。 11/30 09:23
3F：→ tzuchun42: 對 其實我剛剛想到了 如果graph edge是下一個vertex的 11/30 10:35
4F：→ tzuchun42: 值就可以了 11/30 10:35