Finding the shortest path

Words arrange? :)

We go from the upper left corner and put the cost in the first row of each cell as the sum of cells to the left of it + itself (the first horizontal is reachable only to the left).

Further, in the second extreme left - this is the sum of the cost above it + it itself (only on top), and all others - the minimum value of the path above and on the left.

And so on to the end ... In a word, simple dynamic programming.

Now I will try to sketch on C ++.

Here, on the knee, since you are satisfied with any language ... The path is displayed in the reverse order - from the lower right to the upper left:

 #include <iostream> #include <iomanip> using namespace std; int val[3][3] = { 1, 2, 3, 0, 4, 15, 0, 0, 7 }; int cost[3][3] = { 0 }; int pred[3][3] = {-1}; // 0 - ᢥаег, 1 - б«Ґў int main(int argc, const char * argv[]) { cost[0][0] = val[0][0]; for(int c = 1; c < 3; ++c) { cost[0][c] = cost[0][c-1] + val[0][c]; pred[0][c] = 1; } for(int r = 1; r < 3; ++r) { cost[r][0] = cost[r-1][0] + val[r][0]; pred[r][0] = 0; for(int c = 1; c < 3; ++c) { if (cost[r-1][c] < cost[r][c-1]) { cost[r][c] = val[r][c] + cost[r-1][c]; pred[r][c] = 0; } else { cost[r][c] = val[r][c] + cost[r][c-1]; pred[r][c] = 1; } } } cout << "Total cost: " << cost[2][2] << endl; int r = 2, c = 2; for(;;) { cout << "(" << r << "," << c << ") - "; if (pred[r][c]) --c; else --r; if (r == 0 && c == 0) { cout << "(0,0)\n"; break; } } } 

Recursive variation on the wave algorithm:

 #include <iostream> using namespace std; const int SIZE_X = 3; const int SIZE_Y = 3; const int PATH_LEN = SIZE_X+SIZE_Y-1; struct {int x; int y;} path[PATH_LEN] = {0, 0}; int map[SIZE_Y][SIZE_X] = { 1, 2, 3, 0, 4, 15, 0, 0, 7 }; int find(int x, int y) { int self = map[y][x]; if (x == SIZE_X-1 && y == SIZE_Y-1) { path[PATH_LEN - 1].x = x; path[PATH_LEN - 1].y = y; return self; } if (x == SIZE_X-1) { return self + find(x, y + 1); } if (y == SIZE_Y-1) { return self + find(x + 1, y); } int NEXTSTEP = x + y + 1; int down = find(x, y + 1); int right = find(x + 1, y); if (down < right) { path[NEXTSTEP].x = x; path[NEXTSTEP].y = y+1; } else { path[NEXTSTEP].x = x+1; path[NEXTSTEP].y = y; } return self + min(down, right); } int main() { cout << "Result: " << find(0, 0) << endl; for (int i = 0; i < PATH_LEN; ++i) cout << "<" << path[i].x << ", " << path[i].y << ">" << endl; } 

difficult task, for example, such an array

 1 1 1 2 2 9 1 1 1 

if you immediately go on the cheapest way - on line 1 - then the rest of the way will have to go through the most expensive - with 9th. Or another example

 8 8 8 8 8 8 9 9 9 8 8 9 7 9 8 8 9 9 9 8 8 8 8 8 8 

Despite the fact that 7-ka is the most attractive for the price - in order to go through it, you will have to overcome 2 9-ki (this would be on the topic “you wouldn’t be chased by priest for cheapness” :-) lots of.

In fact, other options than fractal recursion, I do not see, the computational complexity of the algorithm is very high. Fractal algorithms are used to compress images, written many scientific papers on the optimization of these algorithms .