zenerguy32
January 7th, 2009, 02:15 AM
I have a problem I can't seem to figure out. I'm trying to code an algorithm which calculates the longest path(s) from a given list of nodes and their neighbor nodes. I've learned a little bit about Djikstra's and the "traveling salesman" algorithms but those are both meant to calculate the shortest distance between two points. The problem statement would basically be "Given a list of nodes and their neighboring nodes (all one unit away), calculate the longest path(s) that can be taken using any given 'road' only once in each path."
Here's an example. Given this list:
Node : Neighboring Node,Neighboring Node,Neighboring Node
0 : 1,2,9
1 : 0,5,6
2 : 0,3,-1
3 : 2,4,-1
4 : 3,5,-1
5 : 4,1,-1
6 : 1,7,-1
7 : 6,8,-1
8 : 7,9,-1
9 : 8,0,-1
('-1' means no neighboring node)
the algorithm should output:
"0-1-5-4-3-2-0-9-8-7-6-1"
"0-1-6-7-8-9-0-2-3-4-5-1"
"0-2-3-4-5-1-0-9-8-7-6-1"
"0-2-3-4-5-1-6-7-8-9-0-1"
"0-9-8-7-6-1-0-2-3-4-5-1"
"0-9-8-7-6-1-5-4-3-2-0-1"
"1-0-2-3-4-5-1-6-7-8-9-0"
"1-0-9-8-7-6-1-5-4-3-2-0"
"1-5-4-3-2-0-1-6-7-8-9-0"
"1-5-4-3-2-0-9-8-7-6-1-0"
"1-6-7-8-9-0-1-5-4-3-2-0"
"1-6-7-8-9-0-2-3-4-5-1-0"
Note that any given node can be visited more than once, but each 'road' between nodes can only be used once. In the example, "0-1-5-4-3-2-0-9-8-7-6-1" is a valid path. Node '0' is used twice, but each road leading to each of its three neighbors is used only once (0-1, 2-0, 0-9).
I've been trying to code this in VB6 but it's gotten very messy and I think I'd like to try coding it in Python to get it working and then convert it to VB6.
My current method starts at a node and "jumps" to a neighbor node until it reaches a node that's already been used once in the current path, and then jumps backwards until it reaches a three-neighbor-node and takes the second "fork" of that node until it reaches that end. It does this until it's jumped all the way back to the starting node, and then it chooses another starting node and runs again until all three-neighbor nodes have been started from. I guess it's similar to a tree-searching algorithm except the branches can connect to each other.
I've spent a while Googling and haven't found much - most articles I've found deal with finding the shortest path. Any help would be appreciated!
Here's an example. Given this list:
Node : Neighboring Node,Neighboring Node,Neighboring Node
0 : 1,2,9
1 : 0,5,6
2 : 0,3,-1
3 : 2,4,-1
4 : 3,5,-1
5 : 4,1,-1
6 : 1,7,-1
7 : 6,8,-1
8 : 7,9,-1
9 : 8,0,-1
('-1' means no neighboring node)
the algorithm should output:
"0-1-5-4-3-2-0-9-8-7-6-1"
"0-1-6-7-8-9-0-2-3-4-5-1"
"0-2-3-4-5-1-0-9-8-7-6-1"
"0-2-3-4-5-1-6-7-8-9-0-1"
"0-9-8-7-6-1-0-2-3-4-5-1"
"0-9-8-7-6-1-5-4-3-2-0-1"
"1-0-2-3-4-5-1-6-7-8-9-0"
"1-0-9-8-7-6-1-5-4-3-2-0"
"1-5-4-3-2-0-1-6-7-8-9-0"
"1-5-4-3-2-0-9-8-7-6-1-0"
"1-6-7-8-9-0-1-5-4-3-2-0"
"1-6-7-8-9-0-2-3-4-5-1-0"
Note that any given node can be visited more than once, but each 'road' between nodes can only be used once. In the example, "0-1-5-4-3-2-0-9-8-7-6-1" is a valid path. Node '0' is used twice, but each road leading to each of its three neighbors is used only once (0-1, 2-0, 0-9).
I've been trying to code this in VB6 but it's gotten very messy and I think I'd like to try coding it in Python to get it working and then convert it to VB6.
My current method starts at a node and "jumps" to a neighbor node until it reaches a node that's already been used once in the current path, and then jumps backwards until it reaches a three-neighbor-node and takes the second "fork" of that node until it reaches that end. It does this until it's jumped all the way back to the starting node, and then it chooses another starting node and runs again until all three-neighbor nodes have been started from. I guess it's similar to a tree-searching algorithm except the branches can connect to each other.
I've spent a while Googling and haven't found much - most articles I've found deal with finding the shortest path. Any help would be appreciated!