I need to find an algorithm which can calculate the shortest path through a certain number of points in space

[FM82]

Like the topic's title. I need to find the shortest route connecting a certain number of points in a 3D space. Dijkstra's algorithm is not what i need because i do not have graph but simple points.

Thanks in advance for any advices which you can give me.

Francesco

[crossrulz]

I don't see why Dijkstra's algorthm isn't applicable here.  You will just have to do the distance calculations.  Or is there more to the story that you haven't told us.  Maybe a good example of inputs with the expected output would help.

[CMal]

I would take a look at the A* algorithm.  It is an extension of Dijkstra with much better performance.  If you have a 3D grid of points, that can still be represented as a graph.  You just have a path connecting each adjacent node in 3D space.  The LabVIEW Robotics module includes a library for A* with 2D occupancy grids, but I'm not sure if it also supports 3D grids.  You could generate a directed graph that takes the form of a 3D grid.

[FM82]

But the A* algorithm calculate the optimal path between two nodes, am i right? I need to find  the shortest route which pass through certain points. For my application i must pass through this intermediate points.

[GerdW]

Hi FM,

I need to find  the shortest route which pass through certain points.

The "shortest route" between points is a direct line. So just draw some lines between your points and you are done! 🙂

You got several suggestions and each time you say "Nay, that doesn't fit to my application!". But when asked for a specific example you don't provide it (nor substantial information)!

[FM82]

First of all thank you for your replies.
I'm sorry but evidently I can't explain me. I try again: I have a camera mounted on a motorized axis system. The axis move the camera while it takes photos of electronic components for further elaboration. The system is programmable by the user which can define the camera position and the type of elaboration. I can't pretend that the user move the camera through an optimized path in a 3D space so I need to elaborate the programmed path and minimize the route through space. The points where the camera take the picture are mandatory and I can't overpass them. The algorithm you proposed search the shortest route between a start point and an end point but cannot guarantee me the all the points define by the user are reached, am I right?
I am out now and I can't give you more details but as soon a reach my computer I will try to explain me better.

[GerdW]

Hi FM,

The algorithm you proposed search the shortest route between a start point and an end point but cannot guarantee me the all the points define by the user are reached, am I right?

Well, when you draw a line between EACH point in your route you are still finished with your task…

[FM82]

Hello again, i finally have some time to answer!
There is something that i can't understand or explain. Obviously the shortest route between two points is a straight line. So i can simply go for a local optimum and moving to the next closest point from where i am. The procedure is pretty simple but: who can guarantee me that a local optimum bring to a global optimum path, for visiting all the points in space, that i need?
I don't know if you ever see an In Circuit machine for testing electronic board. The software, after you programmed it, calculate the optimum route to minimize space travelled and time of test.

Thank you.

[CMal]

If I understand you correctly you have a set of points in space, and you need to travel through each point once with the shortest possible overall path.  This is the traveling salesman problem, and there are many different algorithms to solve it, depending on how many points you have.  I don't know of any LabVIEW implementations, but there is a wealth of information if you do a search for "traveling salesman".

[Bob_Schor]

I believe that the Travelling Saleman Problem is one of those that is "NP-difficult", with no known polynomial-time algorithm ...

Bob schor