大家好,抱歉我找不到一個版是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謝謝