The shortest route from a combination of several points

[pietrow]

Hi everyone

 

I have a problem with calculating the shortes path from a combination of several points. For 4-5 points i can do it manualy and calculate distance for each combination and sleect shortest. But for more than 10 its kind of impossible to define each possible route manualy, so maybe sommeone know how to do it eg. in loop or something like that.

Generally I have on my possible route single points or double points, like below:

1p - starting point

(2pa 2pb) - two possibilities if first is 2pa then second is 2pb or ine reverse

(3pa 3pb)

4p

5p

(6pa 6pb)

(7pa 7pb)

(8pa 8pb)

9p

(10pa 10pb)

11p - end point

Any advice on how to solve the problem of a large number of combinations?

[mhupp]

14 pages to read over.

https://www.theswamp.org/index.php?PHPSESSID=48p02olnkruljfv4l7fupksnk5&topic=30434.0

 

-Edit

Also search for "Traveling Salesman Algorithm"

Edited January 5, 2023 by mhupp

[pietrow]

Thank you mhupp for answer, I know this solution, but I think that my case is in some way easier, because I have a sort of a fixed path, except at nodes where there are two points to choose from, so i have number of possbile routes that euqal 2^(two point nodes) - in the example above it is 2^6=64 routes. It is still possible to do it manually but one or two more and it will be problem.

 

I think about nested IF functions and function SET to set random variable depending on number of current 2-points node

Edited January 5, 2023 by pietrow

[mhupp]

I think I understand but would be easier with a sample drawing.

[pietrow]

Ok, here is an example.

the main goal is to find every possible connection of the red circle to the green ones as below, then calculate each route and choose the shortest path and return this distance along with a list of points in the correct order for that length.

You can only move trough white dashed lines and magenta lines (magenta points), for example:

- start p1

- choose B1/A1

- if chose A1 then choose A2/A3, if B1 choose B2/B3

- if chose A2, choose 3pa/3pb

- if chose 3pa must choose 3pb, if chose 3pb musy choose 3pa

- choose W2/Z2

- if chose W2 then must choose W1

- choose 2pa/2pb

- if chose 2pa must choose 2pb, if 2pb must choose 2pa

- choose Y2/X2 because only this line is connecting column 2 and column 3

- if chose Y2 must choose Y1

- choose 1pa/1pb

One route is done, in his case it could be (p1 A1 A2 3pa 3pb W2 W1 2pa 2pb X2 X1 1pb 1pa)

And all possible routes

 

Now after writing this I realized than i can do this with if loop without declaring 64 variables, 4 will be enough, like Dist Path_list Shortest_dist and Shortest_path_list.

Nevertheless, do you have any idea how to do it faster or smarter, espescially if there are pair of points

 

Example.dwg

[mhupp]

2 hours ago, pietrow said:

Now after writing this I realized than i can do this with if loop without declaring 64 variables, 4 will be enough, like Dist Path_list Shortest_dist and Shortest_path_list.

Nevertheless, do you have any idea how to do it faster or smarter, espescially if there are pair of point

 

Still has potential not to find the shortest path if you default to the shortest distance between points. You have to check each path and add up the total distance and compare.

Because leg one could be shorter in p1 A1 but then all other legs are longer. in that if you when p1 B1 the first leg is longer but the difference is made up over the total distance that it ends up being shorter.

 

Maybe someone smarter then me can figure this out @marko_ribar perhaps.

 

 

 

 

[BIGAL]

Like Mhupp this has been asked before, just a comment look at the GPS on the dash of your car or phone. It has the algorithm worked out. Check when googling Forums/autodesk answers are there.