Cost-Distance and Least-Cost Paths

Finding optimal routes across variable terrain

Published

February 27, 2026

The Trans Mountain Pipeline expansion, approved in 2019 and completed in 2024, required routing 1,150 km of new pipeline from Edmonton to Burnaby through some of the most topographically complex terrain in North America. The route had to balance multiple competing cost surfaces: slope (steep terrain means expensive construction and higher risk), proximity to existing infrastructure (cheaper where right-of-way already exists), geological hazards (landslide-prone slopes, river crossings), and environmental sensitivities (avoiding wetlands, fish-bearing streams, and protected areas). The final route is not a straight line — it is the minimum-cost path through a multidimensional cost surface, exactly the problem that Dijkstra’s algorithm was designed to solve.

Cost-distance analysis extends the simple Euclidean distance buffer by replacing distance with a generalised cost that varies across the landscape. Instead of asking “how far is it?”, it asks “how expensive or difficult is it to reach?” — where the cost per unit distance varies by terrain steepness, land cover, regulatory restriction, or any combination of factors that can be encoded in a raster. The accumulated cost surface assigns a total cost to each cell: the minimum cost of reaching that cell from the source. From the cost surface, the least-cost path — the route that minimises total cost from source to destination — is found by tracing the steepest descent on the cost surface back to the source. The underlying algorithm is Dijkstra’s shortest-path algorithm on a grid graph, one of the most important and widely implemented algorithms in computational geography.

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.

Cost Surface Logic

The Best Route Minimizes Total Resistance, Not Straight-Line Distance

Least-cost paths bend because the algorithm is balancing cheap terrain against expensive terrain. A longer route can still be better if it avoids enough high-cost cells.

source
destination
high-cost barrier
Low cost: easy terrain or preferred land cover.
Medium cost: workable but less efficient to cross.
High cost: steep, hazardous, or restricted terrain.
Least-cost path: optimal route through the accumulated cost surface.
Mental model

Dijkstra On A Grid

Think of each cell as a node. The algorithm spreads outward from the source, keeping the cheapest known way to reach every next cell.

Least-cost routing chooses the path with the smallest total accumulated resistance, which is often not the shortest geometric line.

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 = 3$ - dist[0,1] = 0 + 3 = 3

Update (1,0): - Edge cost = $1 = 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 = 1$ - dist[1,1] = 1 + 1 = 2

Update (2,0): - Edge cost = $1 = 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.

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:

  1. Create cost surface from habitat suitability
    • Low cost: Forest, grassland
    • High cost: Urban, agricultural
    • Infinite: Highways (impassable)
  2. Compute accumulated cost from source habitat
  3. Find least-cost path to destination habitat
  4. 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