# Trying to make a pathfinding algorithm to sort a list of locations by the shortest path that hits all locations

I have a working shortcut right now that just gives me the list of locations in order of the shortest distance from my current location to a 10th of a kilometer.

I have previously visited locations stored by a keyed name with longitude and latitude coordinates saved in the dictionary in data jar. I then have another list in data jar of locations that I need to visit by the keyed name. My distance formula shown below is how I’m calculating the distances from the dictionary values.

in order to speed up the run time of the shortcut I read them in from data jar once by reading the dictionary level above them And then passing the information to my distance formula shortcut to get 10th of a kilometer integers to sort.

I’m having trouble implementing a pathfinding algorithm that can do the calculations for all the different possible routes with just the shortcuts native capabilities for speed. I made a version of a stack based route by writing out to data jar but it took forever to run.

Any suggestions would be much appreciated

It sounds like you are solving the travelling salesman problem, so generally speaking that’s a computationally hard task and does tend to take a little time to run.

Do you know exactly what in your shortcut is running slow?

E.g.

• Is it the calculation you shared above?
• is it a loop that is just churning through dozens of sets of operations?
• Is it the retrieval of geolocation data?

You may be able to improve performance by doing things like:

• Utilising JavaScript steps in the Shortcut for computationally intensive aspects (the JavaScript browser engine is highly optimised for performance on i*OS. You could use Scriptable, or natively.
• Caching location data in Data Jar or the like so you don’t grab it from an address every time you run it.
• Using a different algorithm than your stack based approach (see the Wikipedia article above for some alternative options).
• Offloading computation to a web service or other personal device (a Mac) - with access to other efficiency options, such as implementing the calculations in. A different (faster running) language and returning the results.

https://dev.routific.com/use-cases/travelling-salesman-problem

Hope that helps.

1 Like

The parts that slow it down the most are when shortcuts is calling out for my location at the beginning of the app and any read/writes to data jar. The calculations are extremely quick but everything I have tried in order to implement a stack of arrays with shortcuts variables never seems to work. I don’t know if I’m running into a memory limit, a bug within the variable handler or I just haven’t wrote it correctly. I have gotten the stack to function correctly if I write out to data jar to manage the current state. But all of the calls for popping the stack and adding to the stack introduce the call out latency that I noticed whenever shortcuts interacts with a non-native function.

The reason I switched to the latitude and longitude calculations is because they can run with no or very little overhead. Originally I was trying to actually use street distance in order to do just the simple list of which destination is closer. Every single time you called it, you are waiting three to four seconds or more for response depending on the network.

I pull in all the previous locations with one read from data jar each and then process it by using the dictionaries get keys to create my list of locations and the locations I need to go to.

I guess I forgot to mention that I’m limiting it to a subset of the 6 closest locations in order to prevent the runaway computation of dealing with a factorial (720 for 6) of solutions to check. If I’m able to get the variable management issues worked out, I plan on checking the runtime and adjusting my subset size up based on compute time.

But given the fact that this shortcut will be run each time I navigate to the next destination. The issue of the subsets not including the whole list will eventually be taken care of as I remove destinations off the list. While this won’t give me the optimal solution for the whole problem, it will give me an optimal solution for the subset and then when I I’m ready to run it again. I’m updating my current location and running an optimal solution for the next subset. When the shortcut actually runs I’m given the whole list by distance from my current location but the top six in that order have been rearranged for an path back to endpoint at the end of the day. This allows me to prioritize locations that are not the optimal route if I need to. I’m trying to build a usable shortcut not solve a computer science conjectures after all.

Whenever things get more complicated, I just use pythonista. Makes most things easier.

You could write all the locations to a file (getting locations is probably easier in shortcuts), and then do the algorithmic part in pythonista.