shortest path over a cost raster between two points

[DirkStelder]

Hi everyone,

as always simple questions may have difficult answers. I just have this:

1) a set of 400 points, for which I need to find the shortest paths between them over a cost raster. Not really the path itself but just the total cost of the path.
2) a cost raster

If I do spatial analyst/shortest path I cannot specify " from" and "to" , just a source. I now choose one location, make it a separate point file and run it with this one as the source, but that in effect leads to calculating the SP for each individual cell of the reference raster (= cost raster with 44 million cells) to that single location (takes 10 minutes for that one alone!). I just need to do that for the 400 cells that matter. Now my code runs 48 hours because of all these superfluous calculations.

So in short: whats the code for the SP from a single point A to a single point B over a cost raster?

thanks for any help on this

cheers,
Dirk

[DirkStelder]

Thanks Bill,

indeed you need the info of the whole cost raster because you don't know where the shortest path will go. My understanding of what is going on, however, is that the long computing time does not stem from that but from the fact that the SP's from ALL raster cells to the source point are calculated. My result should not be 44 million numbers but just one: the length of the SP from point A to point B. Because I cannot specify a "from" point and a "to" point but just a source the result now is that I get 44 million SP's of which I only need to know one.

[DirkStelder]

Thanks for your clarification Bill.

I found an older discussion on this with one of your contributions
(http://forums.esri.com/Thread.asp?c=93&f=995&t=151830&mc=8#443651) which describes exactly what I had in mind of doing with some other software. What we should have in this case is defining the graph only once over the 44 mln raster cells, and then do the loop (assuming SP(i,j)=SP(j,i):

for i=1,400
   for j=i,400
        findSP(i,j)
   end
end

What I have to do now in ArcGis is defining the graph 400 times, set each time the next location as the source and get all 44 mln SP's.

That cannot be efficient, but anyway, I followed your tip on creating "holes": the raster, which is a road raster, now has Nodata for all non-road cells. doing one run for one source now is 1 minute so I'm fine.

thanks again but really somebody should find a more efficient way

[DirkStelder]

😉 Yes of course! But just for fun a little more background on this: we are working on digitizing historical road maps and found that just drawing lines of different colours and converting them into a costraster saves a lot of time compared to building a full network. The costraster has all the information so  "letting the mouse look for the cheese" over the raster does the same job as network analyst. Here's one we did for the Netherlands for 1848. Only the drawing alone took more than a week and making it a perfect network would add another week or more.

http://www.regroningen.nl/stelder/1848.jpg

cheers
Dirk

[DirkStelder]

😉 Yes of course! But just for fun a little more background on this: we are working on digitizing historical road maps and found that just drawing lines of different colours and converting them into a costraster saves a lot of time compared to building a full network. The costraster has all the information so  "letting the mouse look for the cheese" over the raster does the same job as network analyst. Here's one we did for the Netherlands for 1848. Only the drawing alone took more than a week and make it a perfect network would add another week or more.

[IMG width="500" height="699"]http://www.regroningen.nl/stelder/1848.jpg[/IMG]

cheers
Dirk

[DirkStelder]

Yes all non-road cells are NoData and all roads are just one cell wide. With one source point I do Costdistance which takes 45 seconds -not bad-. The only thing is I have to do that 400 times, which I do with Python. Some people say Python is very slow;)