bI 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.
pLook up depth-first search (DFS).
bI 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?
bCould you give some example, please?
bLet'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.
bDo 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.
bThe 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.
bWhen 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?
bThe 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?