# Shortest raster path

I am trying to create a path from the blue square to all the green dots. The blue square represents an existing road and the green dots represent centroids of forest stands. The total path distance shall be as short as possible and the path shall be the least cost-path (based on Slope Raster). The least cost path can be done with ArcGIS Cost Path. But I don't know how I could create the shortest possible path.

-
It depends on what you mean by "path": are you looking for the Steiner Tree, to solve the Traveling Salesman Problem, to find four separate shortest paths from the square to the points, or something else? – whuber Jun 13 '13 at 17:46
@whuber I think I am looking for a Steiner Tree. – ustroetz Jun 13 '13 at 17:53
The Wikipedia article I linked to points out that this problem is NP-hard. (That's not a problem with five points but it is for medium to large numbers of points.) It gives a reference to an approximate solution. Your best best in ArcGIS is to check first whether anyone has shared code on ArcScripts. Presuming they haven't, you need to look for code outside ArcGIS or write it yourself. – whuber Jun 13 '13 at 18:10
Okay cool. I will read that article and I think I write it myself. Thanks for pointing these two two thinks out. – ustroetz Jun 13 '13 at 18:11
With no Answers offered in almost a year, and some very useful advice having already been provided as Comments, would you be able to either write up an Answer, or edit your Question to revise it in line with your learnings. For example, it looks like it could be focussed on Steiner Trees now. – PolyGeo Apr 4 '14 at 23:25

The approach I ended up using is the following:

1. I buffer the forest stands, which are represented as centroids (green dots) in the image above.

2. I create a fishnet grid over the entire area of interest.

3. I determine for each fishnet grid cell, how many timber stands are within that grid cell.

4. I determine the grid cell with the highest number of stands within the cell and create a least cost path to that cell from the existing road (blue square).

5. I remove all forest stands, that are now connected to the existing road (blue square) and repeat step (4.) until all stands are connected to the network.

This graphic visualizes the process.

The code to this project can be found on GitHub.

-