2

I need an algorithm to find least cost paths between points on a discrete grid,

  1. allowing for the direction of transport to affect the cost of transport,
  2. allowing for different modes of transportation which connect in some directions and not in others, and
  3. allowing for "transshipment" costs for switching modes of transport.

For this particular application, I need the algorithm to be blazing fast as it will be executing many, many times as part of a larger optimization routine.

For MATLAB, I have found a C-based (MEX) implementation of the Fast Marching Method, which with a bit of modification I have succeeded in generalizing to a Djiktra's Algorithm implementation with the features I need. This is fast enough, but it would be cleaner and more convenient to be able to run my entire optimization routine out of QGIS, as this is where a lot of my data needs to be processed anyway.

What are my options? What do you recommend?

2

There are two modules in QGIS Python included:

Both modules are efficient and written in C.

  • Wow, great, these sound just like what I was looking for. Especially the SciPy one sounds promising. For some reason I couldn't find these by googling... I kept getting results with implementations written in Python. I'll test these and report back. – Matt D. Jul 15 '16 at 13:15
  • The SciPy Dijkstra's algorithm works quite well. Thanks! – Matt D. Aug 1 '16 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.