作者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/cn.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