[問題] minimum cost problem & DAG graph short

看板Prob_Solve作者 (TzuChun)時間5年前 (2018/11/30 07:20), 編輯推噓1(103)
留言4則, 2人參與, 5年前最新討論串1/1
大家好,抱歉我找不到一個版是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://www.ptt.cc/bbs/Prob_Solve/M.1543533604.A.218.html

11/30 09:22, 5年前 , 1F
你的graph的做法長度是不是都是終點的值減起點的值,如
11/30 09:22, 1F

11/30 09:23, 5年前 , 2F
您的例的長度是 2-11=-9,與中間經過哪些點無關。
11/30 09:23, 2F

11/30 10:35, 5年前 , 3F
對 其實我剛剛想到了 如果graph edge是下一個vertex的
11/30 10:35, 3F

11/30 10:35, 5年前 , 4F
值就可以了
11/30 10:35, 4F
文章代碼(AID): #1S07Ga8O (Prob_Solve)