algorithm problem on paths

[mimis]

I am trying to solve an algorithmic problem.

First of all the user inputs the coordinates of some nodes.
I have to go to the node with the biggest x( let name it E) and then to return to the start that will always be the node (0,0)( let name it S).
In this cycle i have to pass from all the nodes but there are some restrictions. When i go to the E i should go along x axes and xprevious<xnext ( i should go only toward nodes with bigger x than x of my current node). When I return to S is the same process but xprevious>xnext.

I have to find the shortest path to do that cycle.

Somewhere i found that i have to use dynamic programming but i am not so good in that and i didn't found many information for that solution.

Can you help me to figure out how to solve that?

Thanks in advance.

[GDICommander]

Do a search on the Djikstra Algorithm for Graphs. Enter it on Google.

[mimis]

Do a search on the Djikstra Algorithm for Graphs. Enter it on Google.

I had already search for Dijkstra's algorithm but in the examples I have found so far a node have connections to some of the other nodes, not in all the other nodes like in my problem.

Can you help me more please?

[GDICommander]

Maybe one of these algorithms will do the trick for you.

http://en.wikipedia.org/wiki/Category:Graph_algorithms

There are plenty of existing algorithms on the graph theory.

Good luck, you will need it.

[VernonDozier]

I am trying to solve an algorithmic problem.

First of all the user inputs the coordinates of some nodes.
I have to go to the node with the biggest x( let name it E) and then to return to the start that will always be the node (0,0)( let name it S).
In this cycle i have to pass from all the nodes but there are some restrictions. When i go to the E i should go along x axes and xprevious<xnext ( i should go only toward nodes with bigger x than x of my current node). When I return to S is the same process but xprevious>xnext.

I have to find the shortest path to do that cycle.

Somewhere i found that i have to use dynamic programming but i am not so good in that and i didn't found many information for that solution.

Can you help me to figure out how to solve that?

Thanks in advance.

As I mentioned in your other thread:

http://www.daniweb.com/forums/thread176078.html

you need to articulate the problem more carefully. This is a graphical problem. It's hard enough to visualize with just a written description. It's impossible to visualize with imprecise language:

In this cycle i have to pass from all the nodes

What does this mean? All nodes must be visited once and exactly once?

i should go along x axes

So y is equal to 0?

Can x be negative? Can y be negative? Can y be non-zero? This is a paper and pencil exercise first. You need to really nail down the problem, and that is before you even get to the programming part of it. All we know is what you describe, so you must be precise and give examples.

[mimis]

All nodes must be visited once and exactly once?

Yes

So y is equal to 0?

No

Can x be negative?

No

Can y be negative?

Yes

Can y be non-zero?

Yes

Sorry that i didn't post these information from the beginning.
I hope these will help.

[GDICommander]

I remember my algorithm course at university. It was tough, at the beginning, but with determination and a little thinking, I found the graph chapter very easy.

What you need is a very graphical view of the situation and a little creativity. You must be capable of doing this, alone is the best. All I can do is to provide links to existing graph algorithms. If you really want to see the solution, take some paper, some pencils and some hours of hard work, and you will get it.

I hope that you are not beginning this homework late, because an algorithm can be long to find.

[mimis]

While I was searching for a useful algorithm i found Floyd Warshall's algorithm and it seemed that it match with my problem.

Do you think that i could implement it in my problem?

[skatamatic]

#include <vector>
#include <algorithm>
struct Point
{
     public int _iX, _iY;
     Point(int x, int y)
     {
          _iX = x;
         _iY = y;
     }
}

bool operator<(Point const & lhs, Point const & rhs)
{
    return lhs._iX < rhs._iX;
}
int main()
{
    vector<Point> Points;
    //insert code to fill node vector here
    Sort(Points);        
    for (int i(0); i < Points.Size(); ++i)
         std::cout <<  Points[i]._iX << ", " << Points[i]._iY << endl;
    for (int i(Points.Size()); i >= 0; --i)
         std::cout <<  Points[i]._iX << ", " << Points[i]._iY << endl;
     return 0;
}

I think that's what you're trying to do. I haven't used C++ in a long time, so my STL syntax might be a bit whacky. Unless this is specifically an assignment for developing a sorting algorithm, leveraging the STL is usually the best way to go about something like this.

The Sort() function (in algorithm.h) leverages a defined operator< to sort from smallest to greatest, so I defined one to spec (returns true if x left hand side is less than x right hand side). Then presto, your assignment is done in about 5 lines.

[monkey_king]

So it's a minimum spanning tree right?

if so use either kruskall or prim
http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/index.html

But don't bother with the implementation just use boost.

[mimis]

skatamatic i have already sorted the points but i haven't found how to find the shortest cycle.
monkey_king it is not spanning tree. It is a cycle and i have to make it without using boost.

[skatamatic]

What do you mean the shortest cycle? What makes a cycle? I imagined you where iterating through each point, making sure that the next x is greater than the current, which is essentially just sorting. You're going to have to describe the problem in greater detail. Are you perhaps generating the shortest path between s and e, by skipping out on nodes that would cause the path to be longer?

[mimis]

What do you mean the shortest cycle? What makes a cycle? I imagined you where iterating through each point, making sure that the next x is greater than the current, which is essentially just sorting. You're going to have to describe the problem in greater detail. Are you perhaps generating the shortest path between s and e, by skipping out on nodes that would cause the path to be longer?

I have to pass from all the nodes with such way that i will do the shortest cycle.

[skatamatic]

That really isn't anymore descriptive. If all nodes must be passed, then there is no shortest cycle, they will always be the same, unless your definition of cycle is different than mine. Mine is: traverse from start to end and back.

[skatamatic]

I think i may understand your problem. You have a grid (not a function) where points can be all over the place , and you need to find the shortest path. Sorry for misunderstanding. I will think up a solution for this problem.

[mimis]

That really isn't anymore descriptive. If all nodes must be passed, then there is no shortest cycle, they will always be the same, unless your definition of cycle is different than mine. Mine is: traverse from start to end and back.

Yes but there are 2^nodes ways to traverse from start to end.
How can i find the correct?

[VernonDozier]

Yes but there are 2^nodes ways to traverse from start to end.
How can i find the correct?

No there aren't. There are (n-1)! ways to go through n nodes, visiting each node once and only once, given a particular starting node as one of the n nodes, as you have in this case. In your case, given your restrictions, the vast majority of these paths are illegal. If no two nodes have the same x value, you have one, count 'em, one, legal path. You need to sit down with paper and pencil and draw it out, because you do not understand the problem.

[mimis]

I thought to make a tree that will have each possible path to go from S to E.
An example is here:
http://www.mypicx.com/03022009/shortest_cycle/

My attemp to build the tree is this:

#include <cstdlib>
#include <iostream>

using namespace std;

class Node
{
public:
int ID; //data item
int n;
Node* pChildrens[]; //ptr to next link in list

Node(int id, int number) //constructor
{
ID=id;
n=number;
for (int i=ID+1;i<=n;i++)
pChildrens[i-ID]=NULL;
}
}; //end class Link

       
void Tree(int id, int n)
    {
    for(int i=id+1;i<=n;i++)
    {
    Node* pNewNode;
    Node* pCurrent;
    pCurrent->ID=id;
    pNewNode->ID=id+i;
    pCurrent->pChildrens[i]=pNewNode;
    Tree(i,n);
    }
    }
               
int main()
{
    Tree(0,5);
    system("PAUSE");
    return 0;
}

But it doesn't work and i don't know why.
Can you see any mistake?

Do you think that a tree with the right implementation could solve the problem?

[VernonDozier]

I thought to make a tree that will have each possible path to go from S to E.
An example is here:
http://www.mypicx.com/03022009/shortest_cycle/

But it doesn't work and i don't know why.
Can you see any mistake?

Do you think that a tree with the right implementation could solve the problem?

A tree will have exactly one path from one node to another. Thus, any problem involving more than one possible path will not involve a tree. Also, only a trivial tree where each node can have only one child (which is a linked list) will visit each node once and only once.

Your code and the "tree" you posted don't take into account the fact that two nodes are connected only if there is no third node with an x value that is between the two nodes' x values. Thus, you can't travel directly from node 2 to node 5 in your graphic, so they need to not be directly connected, as they currently are.

You also have multiple nodes with the same value in the graphic your wrote, so I don't know what it's supposed to represent.

[skatamatic]

A tree will have exactly one path from one node to another. Thus, any problem involving more than one possible path will not involve a tree. Also, only a trivial tree where each node can have only one child (which is a linked list) will visit each node once and only once.

Your code and the "tree" you posted don't take into account the fact that two nodes are connected only if there is no third node with an x value that is between the two nodes' x values. Thus, you can't travel directly from node 2 to node 5 in your graphic, so they need to not be directly connected, as they currently are.

You also have multiple nodes with the same value in the graphic your wrote, so I don't know what it's supposed to represent.

I think he means a min-max tree concept, where the starting node would be the starting position, each leaf would be a possible place to move to, which would leaf out also into further possible paths etc. Then a weight would be put on each potential path based on number of nodes to the end, and you would then have the shortest path.

[VernonDozier]

I think he means a min-max tree concept, where the starting node would be the starting position, each leaf would be a possible place to move to, which would leaf out also into further possible paths etc. Then a weight would be put on each potential path based on number of nodes to the end, and you would then have the shortest path.

Hmmm. I think you may be on to something. I was assuming he was referring to a plain old regular tree, so it didn't make much sense to me. The graph (and now the restrictions in the problem and hence the problem itself) look different to me now.

[mimis]

skatamatic understood what i thought to do.

Can you help me with the implementation of this thinking?

[mimis]

I noticed that this problem is well known as "bitonic tours".
I tried to make an algorithm using dynamic programming.

My attempt is this:

for (int i=0;i<=N;i++)
     {
         for (int j=i+1;j<=N+1;j++)
         {
             if (i==0)
             {
                     if (j==1)
                     L[i][j]=distances[i][j];
                     else
                     L[i][j]=L[i][j-1]+distances[j-1][j];
             }
             else if (i<j-1)
                     L[i][j]=L[i][j-1]+distances[j-1][j];
             else if (i==j-1)
             {
                       if (i==1)
                       L[i][j]=L[0][1]+L[0][2];
                       else
                       {
                       k=0;
                       for (int z=1;z<i;z++)
                       {
                           if (L[z][i]+L[z][i+1]<L[k][i]+L[k][i+1])
                           k=z;
                       }
                       L[i][j]=L[k][i]+L[k][i+1];
                       }
              }
                       
         }
     }

distances[][] is an array that have the distances between each pair
and L[][] is an array to calculate the shortest path.

But this outputs wrong results.
I think that the problem is in the case i==j-1.

Can you see anything wrong and can you help me to fix it?