The task is to use dynamic programming to find optimal routes. This is done by calculating the minimal sum that can be obtained and then find paths which gives that sum.
I coded the input capture part, computated the sum and obtained a list of the nodes that has to be traversed. My problem is when it comes to display the paths.
The idea is like this (Example):
Code:
2 5
8
1 3 6 10
9
4 7
These are the nodes and the objective is to go from Node 1 to Node 10.
Each column represent a level. In level 1 there is Node 1, level 2 there are Node 2,3,4, and so on..
Nodes from a level L are connected to all Nodes found on L+1. This imply that you cannot go from Node 2 to Node 9 directly for example. Each connection has a value which can represent cost for instance.
My code manages these restrictions and captures user input to calculate the minimum cost. These values were obtained, from the procedure used, from an example :
Code:
1 - 2 3 4
2 - 5 6 7
3 - 6 7
4 - 6 7
5 - 8 9
6 - 9
7 - 8 9
8 - 10
9 - 10
this is read as : from 1 i can go to either 2 or 3 or 4 and from 2 i can go to 5 or 6 or 7 and so on..
The data is stored in a structure :
Code:
struct X
{
int Count;
int * List;
};
X * XL;
XL is set for the number of nodes, Count indicates how many nodes are listed in List.
The optimal routes is obtained using these data.
optimal routes are:
Code:
1-2-5-8-10,
1-2-5-9-10,
1-2-6-9-10,
1-2-7-8-10,
1-2-7-9-10,
1-3-6-9-10,
1-3-7-8-10,
1-3-7-9-10,
1-4-6-9-10,
1-4-7-8-10,
1-4-7-9-10.
Am stuck at the listing part. I know it can/should be done with recursion or can be done with iterations. But i cant figure it out. The issue is that the size of the problem is variable, the user can input any number of levels and nodes, so i dont know in advance the depth to look for nodes. Please note that it may happend that there is only one route possible and thus recursion is not needed.
Can anyone please suggest some algorithms or codes to list these paths?