How to calculate shortest path

To calculate the shortest path between two pixels:

prepare two source maps for two distance calculations;

the first source map only contains a start pixel, all other pixels are undefined.
the second source map only contains an end pixel, all other pixels are undefined.

prepare a weight map in which less accessible pixels have higher weight values.
perform two distance calculations, one on the first source map, and one on the second source map.
sum the two output maps of the distance calculations.

The minimum value in the summed distance maps indicates the shortest path.

1. Preparing two source maps:

By using a background map on which you can easily identify start and end points, you will create two new point maps. In the first point map, you indicate a start point; in the second point map you indicate an end point. Both point maps are then rasterized. They will serve as input source maps for distance calculations.

If you wish, you can also directly prepare two raster maps on the background map with start and end pixels; however, point maps are handier for display purposes later on.

Display a map on which you can easily find a start point and an end point.
In the map window, open the File menu and choose Create, Point Map.
In the Create Point Map dialog box,

type a new name for the point map, e.g. Start,
accept the default coordinate boundaries for the point map,
click the little create domain button to create a new class domain for the point map.

In the Create Domain dialog box:

type a new name for domain,
select to create a class domain.

The domain Class/ID editor will be opened.

add class start to the domain, and
add class end to the domain.

Close the domain editor and click OK in the Create Point Map dialog box.

The Point editor will be activated.

In the Point editor:

zoom in on the area where the start point is located,
click the Insert Mode button in the toolbar of the Point editor, and
add the starting point. Assign to this point the name Start.

Close the Point editor. Point map Start contains the starting point.

In the same way, prepare another point map, e.g. called End, which will contain the end point. You can use the same domain for the End point map as for the Start point map. In the Point editor, add one point to the End point map and assign to this point the name End.

When finished, rasterize both point maps so that you obtain raster maps Start and End. These maps will serve as source maps during the distance calculations. Make sure that both raster maps are calculated; you can for instance display them, or you can open the properties of the maps and click the Calculate button in the Raster Map Properties dialog box.

2. Preparing the weight map:

Shortest path calculations are most useful when speed or costs are involved. You can then prepare a weight map where the pixel values represent the relative difficulty or the relative extra cost to surpass the pixels. In a weight map, you should use value 1 for normally accessible pixels, various higher weight values for less accessible pixels, and a negative or the undefined value for unsurpassable barriers.

To create a weight map, you can for instance create an attribute column in an attribute table and base weight factors for instance on known land use and then create an attribute map of the weight column, or you can use some MapCalc statements including road maps, rivers, DEM information, etc.

For more information, see Distance calculation : functionality and Distance calculation : travel time map.

3. Performing the first distance calculation:

From Operations menu in the Main window, choose the Distance operation.
In the Distance calculation dialog box:

for the Source Map, select map Start which you created above,
select the Weight Map check box and select your weight map,
type a name for the output map of the distance calculation, e.g. Dist1.

Display map Dist1, so that it is calculated.

4. Performing the second distance calculation:

From Operations menu in the Main window, choose the Distance operation.
In the Distance calculation dialog box:

for the Source Map, select map End which you created above,
select the Weight Map check box and select your weight map,
type a name for the output map of the distance calculation, e.g. Dist2.

Display map Dist2, so that it is calculated.

5. Checking results:

Display maps Dist1 and Dist2, and drag to both map windows the Start and End point maps. In the Display Options dialog boxes of the point maps, clear the Info check box.

In map Dist1, created using the start point, the position of the end point has the value that represents the shortest route to reach this end point.

In map Dist2, created using the end point, the position of the start point has the value that represents the shortest route to reach this start point.

To check the values in the maps, you can use Pixel Info.

6. Summing the output maps of the distance calculations:

By summing the maps Dist1 and Dist2, you will find the shortest path or the area in which any shortest path can be located.

Type on the command line of the Main window:

Path = Dist1 + Dist2

When you did not use a weight map, the shortest path can be found very easily.

Type the following MapCalc formula on the command line of the Main window:

Path2a = MAPMIN(Path) = Path

The resulting Bool map contains True values for pixels containing the shortest path value (this may appear as an area in which any shortest path can be located) and False values for other pixels.

When you did use a weight map, the values in map Path are not real distance values; they are the product of the unit of your weight value (e.g. s/m or $/m) and calculated distances (m). However, when during the preparation of the weight map you used a multiplication factor to obtain whole weight values, you now have to divide map Path by this factor.

Display map Path in a map window with representation Pseudo, and experiment with the display stretch values: you can accept the default minimum stretch value but for the maximum stretch value type a value which is for instance 10% higher than the minimum. This will show all possible fastest or cheapest paths within 10% of the absolute minimum. You will thus be able to identify fast or cheap alternative routes.
To subtract the 'double' weights from each end pixel (as distances are calculated to each pixel from 2 sides), you can type on the command line:

Path2b = Path - (weight * PIXSIZE(Path))

This may slightly improve your results. You can display map Path2b in the same way as above: accept the minimum stretch value and for the maximum stretch value, type a value which is for instance 10% higher than the minimum.

In case you want to obtain a bool map or a polygon map with a single shortest path, and when you have decided until which value your definition of shortest is valid (e.g. from 1255 to 1288), you can type the following MapCalc formula on the command line of the Main window to obtain a map containing the area of the shortest path(s):

Path2c = INRANGE(Path, 1255, 1288)

The resulting Bool map contains True values for pixels containing the shortest path value (this may appear as an area in which any shortest path can be located) and False values for other pixels.

7. Polishing the result:

If necessary, you can enhance a shortest path area by using a Dilate filter. For more information, see Filter operation: functionality.
To make a polygon out of the shortest path area, use the Raster to Polygons operation. When you want to perform this operation on a value map, you have to use the command line instead of the dialog box.