Shortest Path between two points on grid and cover all points

[handasa]

Greetings Everyone

there are many lisp codes that Find the shortest path between connecting a Grid of points or Shortest path between two points Like TSP and Dijkstra’s Algorithm

the problem appears when i need the this short path to cover all other points to have a Start and End connected together through the entire grid as shown in the picture

Any Help?

Thanks in Advance

 

 

[Lee Mac]

You may wish to refer to this thread - the topic has been discussed extensively.

[handasa]

12 hours ago, Lee Mac said:

You may wish to refer to this thread - the topic has been discussed extensively.

this post discuss the challenge to find the shortest path for a loop i.e it starts from a point and cover all points in the list and come to the start point at last

what i aim to is to have a start point and end point and travel from the start point to end point through all other points

Edited November 2, 2018 by handasa

[ronjonp]

Maybe you could use THIS in conjunction with THIS? Better yet, use Elepanov's Triangulate code to generate the network between the blocks then use the the Dijkstra code.

Edited November 2, 2018 by ronjonp

[handasa]

11 minutes ago, ronjonp said:

Maybe you could use THIS in conjunction with THIS? Better yet, use Elepanov's Triangulate code to generate the network between the blocks then use the the Dijkstra code.

I have a list of points lst with n points. Two of these points are X and Y. 
I need to find the shortest path that starts at X, ends at Y and passes through all the points of lst (in any order) visiting  each point  just once

Dijkstra's algorithm and Travelling Salesman algorithm starts at x and ends at x

 

[ronjonp]

After reading your post a bit closer I understand what you want it is bit different. 

[marko_ribar]

And it has to be the shortest path...

I find your request even more difficult than TSP which doesn't have correct solution at least for some reasonable time with some reasonable quantity of points...

So practically you are doomed...

Sorry... :(

[handasa]

48 minutes ago, marko_ribar said:

And it has to be the shortest path...

I find your request even more difficult than TSP which doesn't have correct solution at least for some reasonable time with some reasonable quantity of points...

So practically you are doomed...

Sorry...

Number of points will not be more than 20 points anyway...

No it hasn't to be the shortest path ..it can be the optimum path resulted form running the code say for 10 or 20 seconds if the method you are gonna to use is trail and error or similar methods

[handasa]

@marko_ribar

I found this problem and may be the solution at this link 

https://softwareengineering.stackexchange.com/questions/315836/algorithm-to-determine-the-fastest-route-passing-in-all-points

they described it as NP-Hard problem

but i have no idea how to code it as a lisp

[marko_ribar]

I've just replied here :

https://www.theswamp.org/index.php?topic=54636.msg591196#msg591196

 

HTH., M.R.