← Back to topics
Topic

path algorithm help

b
bour1992
I am trying to make an algorithm for paths in a graph.
The user input some nodes with different x. The beginning node is always (0,0).
Can you help me to make an algorithm that will calculate each possible path from (0,0) to the node with the biggest x when xprevious<xnext?
It don't need to pass from all the nodes.
Thanks in advance.
p
picsel
Look up depth-first search (DFS).
b
bour1992
I will explain my problem a lit bit more.

I have to go from A to B and i have to pass from some nodes. Nodes=n.
First i could calculate the path when i pass from all the nodes. There will be only one such path.
Next i could find the path when i pass from n-1 nodes. There will be n-2 such paths.
I will continue to do that process till i find the path that connect A and B without any other nodes between them.

Always xprevious<xnext and B will have the biggest x.

Is there any way to make an algorithm to do that process?
b
boba5551
Could you give some example, please?
b
bour1992
Let's say we have 5 nodes.
A(0,0), B(1,5), C(3,2), D(4,1), E(5,7).
I want to go from A to E with all possible ways.
For example i can pass from all the point: ABCDE.
I can pass from n-1 point: ACDE,ABDE,ABCE.
I can pass from n-2 points: ABE,ACE,ADE
and finally AE.
b
boba5551
Do you need second number for something? I see that you have mentioned x, that is the first number of pair.

What is maximal number of nodes?

Is order of visiting nodes important? If it is not, then solution is simply 2^(n - 1). If order is important, then it could be solved in O(n^2) by simple DP.
b
bour1992
The maximum number is 200. The order is important because the next step will have greater x than the previous.

I also need all the pair because the actual problem says that i have to found the shortest path to go from (0,0) to the node with the greatest x and then to return to (0,0). I have to pass from all the nodes in this cycle.
When I go to my destination xprevious<xnext and in the my return i pass from all the remaining nodes but xnext<xprevious.
That's why i ask you how to go to my destination from all the possible paths, i would return from all the remaining nodes.

Is there any way to do that?
If there is any other way to do that, plz help me.

I hope you have understand now.
b
boba5551
When I ask about order I was thinking on letters (A, B, C,...).

Ok, the problem that you have is actually :"How many paths do we have in DAG from node S to node E.", ant it could be solved using dynamic programming. Ok, visit nodes from the lowest to highest x and here is how you will calculate number of ways to come to node w.

Suppose that parent nodes (nodes that are adjacent with w and have lower x coordinate) of w are (u1, u2, ..., uk), then number of ways to reach w from S (let it be DP[w]) is
DP[w] = DP[u1] + DP[u2] + ... + DP[uk].

I hope this help. Could you provide link to the problem?
b
bour1992
The problem says that i have to calculate the distance of the shortest path to do the cycle that i described above.

Because i am not so good on dynamic programming can you explain me the process a lit bit more?
b
bour1992
I noticed that this problem is well know as "bitonic tours".
I tried to develop a DP algorithm.

Here is what i tried:

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.

Can you see any mistake in my code because it output wrong results.