[SciPy-Dev] Graph shortest path

[Zachary Pincus]

Just for completeness in case someone comes across this googling, there's also a shortest-paths algorithm in scikits-image ('skimage'). 

That implementation (in cython, also using a heap underneath) is specific for computing shortest paths across a (weighted) lattice (that is, through an numpy array of weights), and so is less general but faster for that specific case.

Zach



On Dec 19, 2011, at 11:03 AM, Warren Weckesser wrote:

> 
> 
> On Mon, Dec 19, 2011 at 6:25 AM, Jacob VanderPlas <vanderplas at astro.washington.edu> wrote:
> Hello,
> A while ago in scikit-learn we implemented an efficient cython graph
> shortest-path search using both Dijkstra's algorithm and the
> Floyd-Warshall algorithm with Fibonacci heaps.  Currently this is
> well-hidden in the scikit-learn utils:
> https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/utils/graph_shortest_path.pyx
> This is the kind of basic algorithm that I think belongs in scipy rather
> than scikit-learn.  I know that some developers have been thinking about
> graph tools for scipy: are there ideas about whether/where the shortest
> path search would fit in scipy?
> 
> 
> Networkx (http://networkx.lanl.gov/) already provides an assortment of data structures and algorithms for graphs.  It is an active, well-documented project.  Personally, I'd rather not start adding code to scipy that duplicates it.   If your code is better/faster/stronger than theirs, why not contribute it to networkx?
> 
> Warren
> 
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-dev