modelling Level 4

Cost-Distance and Least-Cost Paths

Where should a trail go to minimize slope? What's the easiest route for wildlife between habitats? How do you route a pipeline across variable terrain? Cost-distance analysis finds accumulated cost surfaces, and least-cost paths trace optimal routes through them. This model derives Dijkstra's algorithm and implements it on raster grids.

Prerequisites: dijkstra algorithm, graph theory, optimization, dynamic programming

27 Feb 2026 Updated 12 Mar 2026 14 min read

1. The Question

What’s the easiest hiking route from the trailhead to the summit?

Euclidean distance doesn’t account for terrain difficulty:

Steep slopes are harder to traverse
Roads are easier than off-trail
Rivers may be impassable

Cost-distance accumulates travel cost across a surface:

Applications:

Hiking trails: Minimize elevation gain and distance
Wildlife corridors: Connect habitats through suitable terrain
Pipelines: Minimize construction cost (avoid wetlands, steep slopes)
Power lines: Balance distance vs. terrain difficulty
Emergency response: Fastest route considering traffic and terrain

The mathematical question: Given a cost surface (where each cell has a traversal cost), find the minimum accumulated cost to reach any location, and trace the optimal path.

2. The Conceptual Model

Cost Surface

Cost raster: Each cell has a value representing difficulty/cost of traversal.

Examples:

Slope-based cost:

\[\text{cost} = e^{3.5 \times |\tan(\text{slope}) + 0.05|}\]

(Tobler’s hiking function—models walking speed on slopes)

Land cover cost:

Type	Cost
Road	1
Grass	5
Forest	10
Wetland	50
Water	∞ (impassable)

Combined cost:

\[\text{cost}_{\text{total}} = w_1 \times \text{cost}_{\text{slope}} + w_2 \times \text{cost}_{\text{landcover}}\]

Accumulated Cost Surface

For each cell: Minimum total cost to reach it from source.

Initialization:

Source cell: cost = 0
All others: cost = ∞

Propagation: Iteratively update neighbors, choosing minimum cost path.

Result: Raster where value = minimum accumulated cost from source.

Least-Cost Path

Trace route from destination back to source following steepest descent in cost surface.

Backtracking:

Start at destination
Move to neighbor with lowest accumulated cost
Repeat until reaching source

Result: Polyline representing optimal route.

3. Building the Mathematical Model

Graph Representation

Raster as graph:

Nodes: Grid cells
Edges: Connections to neighbors (4-neighbor or 8-neighbor)
Edge weights: Cost to traverse from cell to neighbor

Edge cost from cell $i$ to neighbor $j$:

\[c_{ij} = \text{distance}_{ij} \times \frac{\text{cost}_i + \text{cost}_j}{2}\]

Distance:

Cardinal neighbors (N, S, E, W): distance = 1 (cell size)
Diagonal neighbors: distance = $\sqrt{2}$ (cell size)

Average cost: Use mean of source and destination cell costs.

Dijkstra’s Algorithm

Classic shortest-path algorithm (Edsger Dijkstra, 1956).

Data structures:

dist[v]: Minimum distance from source to node v
visited: Set of nodes with finalized distances
priority_queue: Nodes to process, ordered by distance

Algorithm:

function dijkstra(graph, source):
    dist[source] = 0
    dist[all others] = ∞
    priority_queue = {source: 0}
    
    while priority_queue not empty:
        u = node with minimum dist in queue
        remove u from queue
        add u to visited
        
        for each neighbor v of u:
            if v not in visited:
                new_dist = dist[u] + edge_cost(u, v)
                if new_dist < dist[v]:
                    dist[v] = new_dist
                    parent[v] = u
                    add/update v in queue
    
    return dist, parent

Complexity: $O((V + E) \log V)$ with priority queue

Where $V$ = cells, $E$ = edges (typically 8V for 8-neighbor grid)

For $n \times n$ grid: $O(n^2 \log n)$

Path Reconstruction

After Dijkstra’s, trace back using parent pointers:

function reconstruct_path(parent, source, destination):
    path = []
    current = destination
    
    while current != source:
        path.append(current)
        current = parent[current]
    
    path.append(source)
    return reverse(path)

Result: Sequence of cells from source to destination.

Anisotropic Cost (Direction-Dependent)

Cost may vary by direction:

Uphill vs. downhill:

$\text{cost}_{\text{uphill}} = \text{base} \times e^{k \times \text{slope}}$ $\text{cost}_{\text{downhill}} = \text{base} \times e^{-k \times \text{slope}}$

Wind resistance:

\[\text{cost}_{\text{headwind}} > \text{cost}_{\text{tailwind}}\]

Implementation: Edge cost depends on both source and destination cells plus direction.

4. Worked Example by Hand

Problem: Find least-cost path from (0,0) to (3,3) in this cost grid.

Cost surface:

      j=0  j=1  j=2  j=3
i=0    1    5   10    5
i=1    1    1    5   10
i=2    5    1    1    5
i=3   10    5    1    1

Use 4-neighbor connectivity (N, S, E, W only).

Solution

Initialization:

dist[0,0] = 0
dist[all others] = ∞

Iteration 1: Process (0,0), cost = 0

Neighbors: (0,1) and (1,0)

Update (0,1):

Edge cost = $1 \times \frac{1 + 5}{2} = 3$
dist[0,1] = 0 + 3 = 3

Update (1,0):

Edge cost = $1 \times \frac{1 + 1}{2} = 1$
dist[1,0] = 0 + 1 = 1

Iteration 2: Process (1,0), cost = 1 (minimum unvisited)

Neighbors: (0,0) [visited], (1,1), (2,0)

Update (1,1):

Edge cost = $1 \times \frac{1 + 1}{2} = 1$
dist[1,1] = 1 + 1 = 2

Update (2,0):

Edge cost = $1 \times \frac{1 + 5}{2} = 3$
dist[2,0] = 1 + 3 = 4

Continue…

After full algorithm:

Accumulated cost:
      j=0  j=1  j=2  j=3
i=0    0    3    8   11
i=1    1    2    4    9
i=2    4    3    3    5
i=3    9    6    4    4

Least-cost path from (0,0) to (3,3):

Trace back from (3,3):

(3,3) cost=4, parent=(3,2)
(3,2) cost=4, parent=(2,2)
(2,2) cost=3, parent=(2,1)
(2,1) cost=3, parent=(1,1)
(1,1) cost=2, parent=(1,0)
(1,0) cost=1, parent=(0,0)
(0,0) source

Path: (0,0) → (1,0) → (1,1) → (2,1) → (2,2) → (3,2) → (3,3)

Total cost: 4 units

Path avoids high-cost cells in top-right and bottom-left corners.

5. Computational Implementation

Below is an interactive cost-distance path finder.

Cost type: Connectivity: Show cost surface: Show accumulated cost:

Path length: -- cells

Total cost: --

Avg cost/cell: --

Click to set start (green) and end (red) points, then path will compute automatically.

Try this:

Click to set start (green) and end (red) - path computes automatically
Slope-based: Path avoids steep center (darker = higher cost)
Land cover: Path finds low-cost patches
8-neighbor vs 4-neighbor: Diagonal moves allowed vs cardinal only
Show accumulated cost: Blue (near start) to red (far) - distance from source
Path (orange): Follows minimum cost, not straight line
Notice: Path curves around high-cost areas even if that means longer distance!

Key insight: Optimal path balances distance vs. terrain cost—sometimes the long way is easier!

6. Interpretation

Wildlife Corridor Design

Problem: Connect two habitat patches for animal movement.

Approach:

Create cost surface from habitat suitability
- Low cost: Forest, grassland
- High cost: Urban, agricultural
- Infinite: Highways (impassable)
Compute accumulated cost from source habitat
Find least-cost path to destination habitat
Widen path to create corridor (buffer)

Result: Protected corridor enabling wildlife movement.

Example: Mountain lion corridors in Southern California.

Pipeline Routing

Cost factors:

Slope (steep = expensive construction)
Land ownership (private > public)
Environmental sensitivity (wetlands = regulatory cost)
Crossings (rivers, roads = high cost)

Optimization:

\[\text{cost} = w_1 \times \text{construction} + w_2 \times \text{permits} + w_3 \times \text{maintenance}\]

Least-cost path minimizes total project cost.

Trail Design

Tobler’s hiking function (optimal walking speed vs. slope):

\[v = 6 e^{-3.5|\tan(\text{slope}) + 0.05|}\]

Where $v$ is speed in km/h.

Travel time:

\[t = \frac{d}{v}\]

Trail routing:

Minimize total time
Avoid slopes > 15% (too steep)
Stay near scenic viewpoints (negative cost)

Result: Enjoyable, efficient trail.

7. What Could Go Wrong?

Local Minima

Greedy algorithms can get stuck:

High cost barrier surrounds low-cost destination
Greedy descent stops at barrier (local minimum)
Never finds global optimum (go around barrier)

Dijkstra avoids this by exploring all possibilities.

Diagonal Bias

In 4-neighbor grid:

Diagonal moves unavailable → Manhattan distance artifacts

In 8-neighbor grid:

Diagonal cost = $\sqrt{2} \approx 1.41$ but often approximated as 1.5 or 1

Bias: Paths may zigzag when straight diagonal is optimal

Solution: Use correct $\sqrt{2}$ weight for diagonals

Raster Resolution

Coarse DEM misses fine-scale barriers:

Small cliffs
Narrow canyons
Local hazards

10m DEM: Can route through 5m cliff (invisible at this resolution)

Solution: Use finest available resolution for critical applications

Memory Limits

Large grids require huge memory:

10,000 × 10,000 grid = 100 million cells

Each cell needs:

Distance value (8 bytes)
Parent pointer (8 bytes)
Priority queue entry (variable)

Total: ~2 GB minimum

Solution:

Process in tiles
Use sparse data structures
Hierarchical pathfinding (coarse → fine)

8. Extension: A* Algorithm

A* improves Dijkstra with heuristic guidance.

Heuristic: Estimated cost from node to goal.

For spatial grids: Euclidean distance to goal

\[h(n) = \sqrt{(x_n - x_{\text{goal}})^2 + (y_n - y_{\text{goal}})^2}\]

Priority: $f(n) = g(n) + h(n)$

Where:

$g(n)$ = actual cost from start to $n$
$h(n)$ = estimated cost from $n$ to goal
$f(n)$ = estimated total cost

Advantage: Explores toward goal → faster than Dijkstra

Requirement: Heuristic must be admissible (never overestimate)

For grid: Euclidean distance is admissible (straight line is shortest)

Speedup: 2-10× faster for long paths

9. Math Refresher: Priority Queues

Definition

Priority queue: Data structure supporting:

insert(item, priority): Add item with priority
extract_min(): Remove and return item with minimum priority
decrease_priority(item, new_priority): Update priority

Implementation Options

Array (unsorted):

Insert: $O(1)$
Extract min: $O(n)$ (must scan)

Array (sorted):

Insert: $O(n)$ (maintain order)
Extract min: $O(1)$ (first element)

Binary heap:

Insert: $O(\log n)$
Extract min: $O(\log n)$
Best for Dijkstra

Fibonacci heap:

Decrease priority: $O(1)$ amortized
Theoretical improvement for Dijkstra
Complex implementation, rarely used in practice

Dijkstra with Priority Queue

dist[source] = 0
pq.insert(source, 0)

while pq not empty:
    u = pq.extract_min()
    
    for each neighbor v:
        alt = dist[u] + cost(u, v)
        if alt < dist[v]:
            dist[v] = alt
            if v in pq:
                pq.decrease_priority(v, alt)
            else:
                pq.insert(v, alt)

Complexity: $O((V + E) \log V)$ with binary heap

Summary

Cost-distance accumulates travel cost across variable terrain
Cost surface assigns traversal cost to each cell (slope, land cover, etc.)
Dijkstra’s algorithm finds minimum accumulated cost to all reachable cells
Least-cost path traces optimal route by backtracking through cost surface
Edge cost combines cell costs and distance: $c = d \times (c_1 + c_2)/2$
8-neighbor connectivity allows diagonal movement (more realistic paths)
Applications: Wildlife corridors, pipeline routing, trail design, emergency response
Challenges: Memory limits, raster resolution, diagonal bias
A* algorithm improves performance with heuristic guidance
Critical for infrastructure planning, conservation, and spatial optimization