pathfinding, special case...

[blazer]

this pathfinding problem is a little different to others that are described on the net.

similar to travelling salesman - except for the fact that it starts at the start-node and ends at the end-node (different to start node).

the traveller has to start at the first node, go thru all nodes before ending at the final node - this must be done in the most efficient (shortest) manner possible.


how do i do this?


thanks all...

[OneSadCookie]

It's NP-complete, just like the traveling salesman problem. That means that, for large numbers of nodes, it's probably too expensive to find an absolute-best solution. Depending on how general your network is, you may be able to find easy optimizations to make.

In terms of a basic algorithm, just try all possible paths and keep the shortest.

[blazer]

onesadcookie - nz huh, me in aus. anyway ... ummm isnt there a better way of doing it other than looking at all paths? a friend of mine said its got something to do with triangles ... do you know much about this bro?

[unknown]

Yes its got somthing to do with triangles..... :wacko:
Just do it osc's way, It will work much faster than you expect unless you have hundreds of nodes then you should try and develop some heuristic.

[Andrew]

Check out Dijkstra's algorithm (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) and some of the other famous shortest path algorithms (http://en.wikipedia.org/wiki/Shortest_path_problem).

[OneSadCookie]

those don't take into account the constraint that you must pass through every node.

the simple algorithm I suggested originally is about as good as it gets, without using some constraint on the problem to simplify the possibilities that need to be checked.

[aarku]

An approach is to use A* to search for the best path of TSP while using the minimum spanning tree as the heuristic.

Wikipedia has info if you need.

-Jon

[aarku]

those don't take into account the constraint that you must pass through every node.

the simple algorithm I suggested originally is about as good as it gets, without using some constraint on the problem to simplify the possibilities that need to be checked.

If "as good as it gets" is equivalent to "brute force" ;-)
-Jon

[GoodDoug]

There is no algorithm that can find the best path for all cases that will be faster than the brute force method. If you happen to discover one that works in all cases, I'll personally nominate you for the Truing award for this year.

This is a problem that computer scientists have been working on for many years. If your sample set is large enough to make checking every possibility untenable, then there are some heuristics you can use to approximate the shortest path. I guess the first thing I'd try is a modified A* type of thing that looks ahead a certain number of nodes to find the shortest paths in a greedy way. Really, what you have is a very difficult problem and not one that will be easily solved by a complete algorithm, other than the one OSC offered.