CODEWITHSUNDEEP
netlogo
Nell
Nell

Reputation: 559

Least cost path

I have a landscape with several habitats (i.e. polygons with different IDs). Each polygon of habitat is composed of several patches. In addition, each polygon of habitat has an associated cost. I would like to obtain the least cost path between the polygon that contains a turtle and all the polygons that are in buffer of 2 km around the polygon that contains a turtle.

In a first time, I think to use "weighted-distance-to" from NW extension. According to the example associated to this primitive, I should create a link between the polygon that contains a turtle and all the polygons that are in buffer of 2 km, then I should assign a weight value to the link. In the example, each link between two turtles is assigned to one weight value defined by user. In my case, as a link crosses different habitats, is it possible to calculate a weight value equal to cumulative costs along path towards one of polygons that are in buffer of 2 km ?

Thank you very much for your help.

Upvotes: 1

Views: 296

Answers (1)

Jeroen Vuurens
Jeroen Vuurens

Reputation: 1251

Sound like you could create a cool variant of Dijkstra's shortest path algorithm.

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

If you keep all generated paths in a TreeSet sorted on length, you pull the current shortest path, extend it with all possible polygons that have not been visited yet, and push these solutions in your TreeSet. If from a polygon you can only move to surrounding polygons at greater or equal costs than the shortest route you found so far you can drop that route. That way you expand only the shortest routes generating a breadth first search for the nearest turtle, while truncating possibilities that will never work.

good luck!

Upvotes: 1

Related Questions