Fidn the lowest path
Hi all, this is the 1st time I post here. I don't know whether this has been posted before. If such just give me a URL to see.
Well let me start right now.
I encounter a problem which is a conversion of a similiar problem in the national programming competition of Singapore in 1995.
The problem is as follows:
Given a table m x n size filled with value from 0 to 1.
m: no. of row
n: no. of column
Both m and n do not exceed 20.
Find a sequence of cells going from the first cell (top-leftmost) to the last cell (bottom-rightmost) such that the sum of those cells is the smallest one we can find. We can just move through one cell horizontally or vertically at a time.
For example: we have the following table
0.5 0.8
0.2 0.5
0.1 0.7
The sequence of the smallest sum is (1,1)(2,1)(3,1)(3,2), and hence the smallest sum is 1.5 = 0.5+0.2+0.1+0.7 .
(1,1) means the cell located by 1st row and 1st column.
I'm thinking of the way that we'll go through the ways, and find the smallest. But it seems to become complicated when the table size goes bigger but not exceed 20 x 20.
I'm also thinking of using a Graph with Dijkstra method to find but still get stuck.
