Monthly Archives: October 2013

Least Cost Path: Dijkstra’s algorithm

Image

I’ve recently started walking to work, and as a result I’ve started thinking about the easiest way to get there. I’m not sure how much other people think about it, or consciously think about it, but every step and other larger movement decision (where to cross the street, what neighbourhood to visit, etc.) has an associated cost (effort, danger, time, etc.). When you find the optimal route according to your cost assignments, you have found what’s called the Least Cost Path (at least, by ArcGIS), or solved the Shortest Path problem in Graph Theory (which I won’t pretend to fully understand).

Your brain tends to do this fairly easily. We know that it’s easier and safer to walk down a sidewalk than the middle of a street or over top of a building. Perhaps you choose the north sidewalk because it gets more sunlight than the south sidewalk. We also avoid certain routes because they are poorly lit at night.

Our computers have more trouble “just knowing things.” Using GIS software, we can assign costs to a continuous cost surface. In my example, I’ve assigned costs to a section of Prince George, BC (spatial data courtesy of the City of Prince George Open Data Catalogue) as follows: building = 100, street = 15, alley = 5, alley/sidewalk intersection = 3, and sidewalk = 1. The higher the cost, the less you’d want to walk there.

Next, we need to evaluate our route options. You can do this in ArcGIS using the Spatial Analyst toolbox (which ain’t free), but it’s cheaper and more fun to make our own using javascript, Google Maps API (the map), PaperJS (access pixel values from cost raster), and Dijkstra’s algorithm (the math). I won’t go into the details, but you can read the code (Ctrl+u) and try to figure it out for yourself.

My example is here. A word of warning: it’s slow. It takes about 80 seconds to evaluate 1000 potential points in a 10 pixel grid (that is, 10 pixels in the original raster, before it gets blown up to fit the map). The example starts in the top left corner and tries to travel to pixel 250 (right), 250 (down). Potential, rejected sites are grey circles; selected sites are purple filled circles connected by the least cost line.