Finding the shortest path

Dear All,


I would like to get some suggestions from anyone of you to tackle a
particular problem that I am facing.

"I have a set of points in which I know the start and destination
points.I need to find the shortest route connecting all the points".

How do you sort the points?Which algoritm do you think is the most
simpler?

Regards,
nash

 

I'm not sure how you'd do this in microstation programming ..
Maybe you could do it with SQL in Mapinfo
or maybe in Bentley Geo graphics there might be something..
I'm tempted to try to solve it algebraicaly with pythagoras.. from the
difference between the xy of each point and the origin will give the
shortest of the first point, it then would become the new origin and you
then do it again this determines the next point after the new origin, then
you would have the sequence of points to be joined from the origin..in
sequence
would not be too hard to do in excel then use excel to reorder the points
and use place line command and the
place line xy=cordx1,cordy1
place line xy=cordx2,coordy2 etc
save these as txt and then place the line by script keyin @the full path
to mytextfile.txt at the key command line in ustn
It should be easy as you already must have the points in a table or ascii
file just play with it in excel set up formulas so you can recycle it with
the series fill and just pate in new coords each time from another table..
If you don't have the points in a table select the points then use the
export cordinates tool (look in xyz annotations if you never heard of it)..
you could make a series of macros to simplify the whole operation from the
above...
Or you could by soem mapping tools MAPPA might have this feature...
Search for MAPPA on the web.

 

The usual method:

Asumming the points on a grid.

OXXXX
XXXXO
XXXXX
XXOXX

Where 0 are the points. Label the starting point 1 then all it's
adjacent points 2, all points adjacent to those points 3 until you run
into the first other point, then trace the numbers back.

After 2 iterations:

12XXX
22XXO
XXXXX
XXOXX

3:
123XX
223XO
333XX
XXOXX

4:
1234x
2234O
3334x
44O4x


(The o in the bottom row was found in iteration 4)
Now trace back any route 4-3-2-1

To find the route from that point to the next repeat.

This also can be done with descrete points connected by line segments
using the segment's lengths as the number (a weighted path)

I saw a nice java demo of the algorithm on the web demonstrating
routing circuit boards.

-Tim

 

Tim I don't seem to be able to work thru your example to get a shortest
path?
I understand it's an iterative approach

 

I can't say I gave the best description.

See
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml

The algorithm text may be hard to follow, but the java demos make
things pretty clear.

These demos show the weighted case (points connected by lines of
different length), but the same can be done with a grid of points with
a uniform distance between each point.

-Tim