comp.lang.idl-pvwave archive: archive » Least Cost Path using Dijkstra's Algorithm

Home » Public Forums » archive » Least Cost Path using Dijkstra's Algorithm

Show: Today's Messages :: Show Polls :: Message Navigator
E-mail to friend

Re: Least Cost Path using Dijkstra's Algorithm [message #73140 is a reply to message #72978]

Mon, 25 October 2010 17:19

James[2]
Messages: 44
Registered: November 2009

Member

I recently programmed the Fast Marching Method (
http://math.berkeley.edu/~sethian/2006/Explanations/fast_mar ching_explain.html
) as an external C program for IDL. The Fast Marching Method is the
continuous version of Dijkstra's algorithm: it simulates a boundary
moving through space monotonically with speed as a function of
position. The pixel/voxel grid is considered a sampling of the
continuous speed function.

You can find least cost paths by initializing the boundary at a single
point and then backtracking from the destination(s) through the
arrival time field using gradient descent. This will give you
interpolated points that might not be at exact grid points (pixels),
but it sounds like that's what you want. The algorithm is O(n lg n)
where N is the number of pixels, just like Dijkstra's.

Anyway, if this sounds interesting to you, I can send you the C code
and the IDL wrapper function. You can compile it with MAKE_DLL. I
optimized my implementation for sparse data sets (where the speed is 0
in most places), so if you want to travel through the entire
20000*20000 array, it will be slow. I might be persuaded to write a
non-sparse version if your application is interesting enough ;-)

Report message to a moderator

[Message index]

		Least Cost Path using Dijkstra's Algorithm By: Bill[1] on Thu, 21 October 2010 06:03
		Re: Least Cost Path using Dijkstra's Algorithm By: David Fanning on Fri, 22 October 2010 06:31
		Re: Least Cost Path using Dijkstra's Algorithm By: ben.bighair on Fri, 22 October 2010 06:25
		Re: Least Cost Path using Dijkstra's Algorithm By: David Fanning on Fri, 22 October 2010 05:15
		Re: Least Cost Path using Dijkstra's Algorithm By: James[2] on Mon, 25 October 2010 17:19

Previous Topic:	Machine Specific Code
Next Topic:	Re: Machine Specific Code

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

] [

]

Current Time: Wed Oct 08 15:27:24 PDT 2025

Total time taken to generate the page: 0.00607 seconds