Dynammic programming - optimal Routes Listing

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?

So are you trying to find all paths, a shortest path, or all shortest paths? You say you are computing a sum to find the shortest path -- how can you do that if you don't know what path you're adding up? (In other words, if you've done what you say you've done, then you should have already solved the problem, at least for finding the shortest path -- maybe not all paths.)

This is an extract of the output generated :

Code:

---

The map you input is as follows.

Level:1 has 1 Stage(s).
Level:2 has 3 Stage(s).
Level:3 has 3 Stage(s).
Level:4 has 2 Stage(s).
Level:5 has 1 Stage(s).

Number of Policy Decisions (Based on provided Map) : 20

        F4(S,X4) = CsX4 + F*5(X4)
-------------------------------------------------
        | 10    |      f*4(S)  |  X*4
-------------------------------------------------
  8 |    4+0=4            4      10
  9 |    4+0=4            4      10

=================================================



        F3(S,X3) = CsX3 + F*4(X3)
-------------------------------------------------
        | 8    |    9    |      f*3(S)  |  X*3
-------------------------------------------------
  5 |    4+4=8      4+4=8            8      8 or 9
  6 |    6+4=10      4+4=8            8      9
  7 |    4+4=8      4+4=8            8      8 or 9

=================================================



        F2(S,X2) = CsX2 + F*3(X2)
-------------------------------------------------
        | 5    |    6    |    7    |      f*2(S)  |  X*2
-------------------------------------------------
  2 |    6+8=14      6+8=14      6+8=14            14      5 or 6 or 7
  3 |    6+8=14      5+8=13      5+8=13            13      6 or 7
  4 |    5+8=13      4+8=12      4+8=12            12      6 or 7

=================================================



        F1(S,X1) = CsX1 + F*2(X1)
-------------------------------------------------
        | 2    |    3    |    4    |      f*1(S)  |  X*1
-------------------------------------------------
  1 |    4+14=18      5+13=18      6+12=18            18      2 or 3 or 4

---

The execution starts from the destination to end with the starting point to obatin the minimum cost. then from the start point we move to the destination using the Nodes obtained when calculating the min. cost. therefore i cannot know the path until am done with generating these tables. once this part is done the thing to do is display the paths and thats where i am stuck since it involves (surely) a complex recursion.

I hope am expressing myself clearly, if not please let me know.

By the way please dont mind these f*some numbers..thats supposed to be subscripts.

So you're done -- you've got the answers in the right-hand column. It's not so much recursion as printing the right-hand column upside down (or tilted, or whatever). The only hard part for you is dealing with all the possibilities (most shortest-path algorithms only look for any shortest path, instead of all of them).

I suppose in this case I would adapt a little bit -- normally you tag each node with where it comes from, here you would tag each node with a std::list of all the possible places where it comes from. (I say comes from because normally I run the thing forward, instead of starting at the end and working backwards, but it comes out the same in the end.) So node 1 would have a tag of <2,3,4> and node 2 would have a tag of <5,6,7> and node 3 would have a tag of <6,7> and so on. Then you start at node 1 and follow the tags. (If there are multiple tags, you'll have to do a foreach kind of thing.)

Exactly. I have all the required data but dont know how to code it in order to output the found paths. I have tried and got the paths displayed as long as there are no more than 2 sublevels, by simply using nested "for" loops. Am looking for a general algorithm which fits in for any number of sublevels.

Well, there's nothing wrong with recursion here -- at each step you have a current node, and the path so far (in a string, say). If you're on the last level, print out the path and be done with it. Otherwise, for each tag on the current node, put that new step on the path, and call recursively.

I have tried this recursive function. The value of m is 1 when the function is first called.

NumberOfStage delimits the number of Nodes present and XL is a pointer to a struct i mentioned earlier.

Code:

---


void Recurse(int m)
{
  static string ActualPath ="";
  static string RootPath ="";
  char TempStr[4];


          if ( m == NumberOfStage)
          {
              cout<<"1 - "+ RootPath+" - "+ ActualPath<<"\n";
          }
          else
          {     
                for (int u=0;u<XL[m].Count;u++)
                { 
                       
                  itoa (XL[m].List[u],TempStr,10);             
                  ActualPath+=TempStr;
                       
                  if(XL[m].List[u]!=NumberOfStage) 
                    ActualPath+=" - ";

                  Recurse(XL[m].List[u]);

                  itoa (m,TempStr,10);
                  RootPath=TempStr+RootPath;

                }
                     
          }
                       
        RootPath="";               
        ActualPath="";
       
}

---

This is the output i get:

Code:

---


1 -  - 2 - 5 - 8 - 10
1 - 5 - 9 - 10
1 - 2 - 6 - 9 - 10
1 - 2 - 7 - 8 - 10
1 - 7 - 9 - 10
1 - 1 - 3 - 6 - 9 - 10
1 - 3 - 7 - 8 - 10
1 - 7 - 9 - 10
1 - 1 - 4 - 6 - 9 - 10
1 - 4 - 7 - 8 - 10
1 - 7 - 9 - 10

---

A bit confusing, but if you refer to the previous post i made you can actually trace the paths. At places it misses the second Node and other places it displays the second Node while it should not. Furthermore the second Node when shown is incorrect as it says 1 again. I am a bit lost in the recursive process taking place.

Can anyone please point out my mistake? Thanks

I don't know what NewRecurse is, exactly, but: I can notice that in each case, the first thing printed (not counting the 1 - at the start) is always the node before the thing that changed. (So when 2 changed to 3, or when 3 changed to 4, the 1 printed; but not otherwise. When the 6 changed to 7, the <level 2 #> changed, but not when 7 stayed 7, etc.) This leads me to believe that somehow the "static" bit of the path is not getting stored properly.

Perhaps tracing in a debugger will shed some extra light on what RootPath and TempPath etc. are as things get called.

Oh sorry thats supposed to be Function Recurse with 1 parameter of type int. I have corrected it above.
Well your deduction is right. I wanted to use the debugger but find it to be a nightmare with Bloodshed Dev-C++

I manage to debug using Dev-C++. The backtrace shows the right values for the variable m in reverse order but it is not what is being displayed.

Code:

---

void Recurse(int m)
{

          cout<<m<<" - ";   


          if ( m == NumberOfStage)
          {
             
              cout<<"\n\n";         

          }
          else
          {   

                for (int u=0;u<XL[m].Count;u++)
                { 
                       
                  Recurse(XL[m].List[u]);

                }
                     
          }
                       
       
       
}

---

I considered your suggestion about the static variables and instead passed the string to the function again. That solved the problem. Thanks