C-based implementation of Djikstra's or Fast Marching for QGIS/Python?

Question

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?

Answer 1

There are two modules in QGIS Python included:

• Scipy csgraph: http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.sparse.csgraph.dijkstra.html
• NetworkX: http://networkx.readthedocs.io/en/stable/reference/algorithms.shortest_paths.html

Both modules are efficient and written in C.