Printable View
Take for example a text file which contains:
7
6 3
3 8 5
11 2 10 9
Think of the above as a triangle of adjacent nodes.
The minimum path in this case is 7 + 6 + 3 + 2 = 18
If you were to design an algorithmn to specify this, would you compute ALL possible paths and store them somewhere and compute the smallest one at the end?
Is there a quicker way of doing it?
This is the subject of a Project Euler (projecteuler.net) problem, I think (see http://projecteuler.net/index.php?se...problems&id=81 for example of a strongly-related one). If this is a homework problem, you should solve it yourself: you will not learn anything by reading the solution. If, however, you're just doing it for fun and are annoyed that you can't solve it, the solution is as follows:
The central insight is to work backward from the bottom rather than forward from the top. If you go forward, you will have to search a binary tree for the optimal path. If you go backward though you can do by looping through each node only once:
(1) Start at the bottom; all bottom nodes get their own value
(2) On the next level, each node get's it's value set to it's current value + the minimum value of the two nodes below it. The node's value now contains the 'total cost of getting to the bottom if it used a minimum path to get there'.
(3) Repeat this process at each level all the way up to the top node
(4) The top node now contains the minimum cost through the tree; return it