[請問] 演算法問題Minimum cost graph DAG
大家好，抱歉我找不到一個版是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
→
11/30 02:47,
7年前
, 1F
11/30 02:47, 1F
推
11/30 02:53,
7年前
, 2F
11/30 02:53, 2F
→
11/30 07:15,
7年前
, 3F
11/30 07:15, 3F
→
11/30 07:15,
7年前
, 4F
11/30 07:15, 4F
→
11/30 16:13,
7年前
, 5F
11/30 16:13, 5F
→
11/30 16:14,
7年前
, 6F
11/30 16:14, 6F
推
12/01 04:29,
7年前
, 7F
12/01 04:29, 7F
推
12/01 14:25,
7年前
, 8F
12/01 14:25, 8F
→
12/01 14:25,
7年前
, 9F
12/01 14:25, 9F