[SciPy-User] Efficient Dijkstra on a large grid

John Gleeson jdgleeson@mac....
Tue Apr 9 19:09:09 CDT 2013


On 2013-04-09, at 5:07 PM, Chris Weisiger wrote:
>
> Any suggestions?


Hi Chris,

I infer from your code that your edge weights are always equal to 1.  
This is a special case, sometimes called "hop-count shortest path". It  
can be solved with breadth-first search (BFS). The Wikipedia BFS  
article mentions this application.
http://en.wikipedia.org/wiki/Breadth-first_search

-John


More information about the SciPy-User mailing list