Big problem...

[Dragev]

How do I say this?

Let's try...

I'm doing a program that finds a path between two given points. All points have an integer value, and they reside in an array, like this:

100 - 101
100 - 105
100 - 108
101 - 102
101 - 108
102 - 224
103 - 224
...
108 - 120
...
120 - 224


This means that from 100, the path goes either to 101, 105, or 108.

If the given start and end points were 100 - 224, the answer path would be 100-101-102-224 OR 100-108-120-224.

But how do I make this program?
Where do I start?

Thanks in advanks...

D

[paulw]

Are you looking for any path or the shortest path? You could do a brute force search on all possible paths but this rapidly becomes difficult if the number of nodes/chains in each path is even moderately large.

Few more details please, i.e. Number of nodes, limitations on the array, max array entries, length of the path etc.

Cheers,

P.

[klintsovi]

the easiest way is to use prolog (its backtracking facilities)

your paths will be stored as
path(100,101).
path(101,100).
path(101,105).

and so on

the function is

getpath(X,Y).
getpath(X,Y):- getpath(X,Z),print(X),print(" - "),print(Y),getpath(Z,Y).

to find the shortest path is NP complete problem which is best to solved in ECLIPSE prolog.

[Dragev]

Paulw: I'm kinda looking for any path. The Array(2D) have 110 x 3 elements. The path won't have more than 30 nodes.

Klintsovi: Prolog is something I don't know anything about. Please fill me in.

Thanks.

D

[paulw]

I'll think about this one. As Klitsovi says, this is a classic Network Path problem.

Somewhere, way back, I think I wrote some code to create a tree structure to do this. I'll have a look.

Cheers,

P.

[Dragev]

Have you found it yet?

[paulw]

Nope. Too many beers at lunch. Probably be Monday - is that OK?

Basic approach is to define a structure with pointers to the next node, each node also has pointers to the next node etc. Each unique node is a destination so you can set up the start point (root node) and possible destinations, if you have found the destination you then 'walk' back through the pointers to find the route.

Is that clear.

P.

[Dragev]

I'm starting to get the hang of it. I'm doing it backwards, kinda convinced that's the way to do it. Still some debugging left to do (endless loops etc.)

Beer at lunch rules.

D

[klintsovi]

Send us the code or the description of an algorithm it will be quite interesting to see the solution to the problem in VB

[klintsovi]

here is a possibly usefull link

http://hissa.nist.gov/dads/HTML/travelsales.html