shortestPath: Shortest paths on a SpatNetwork

Description

Compute shortest paths between pairs of nodes on a SpatNetwork using Dijkstra's algorithm. The path weight is the sum of net_weights along the traversed edges -- by default this is geometric length in meters (geodesic for lon/lat data, planar Euclidean otherwise), but custom weights such as travel time can be set with net_weights<- or via the weights argument of netw.

The function honours net_directed(net): in a directed network only edges traversed in their stored from_node \eqn{\to} to_node orientation are allowed, which is what you want for one-way streets or stream networks.

The result is a SpatVector of lines that follow the original (sinuous) edge geometries, so that the returned features can be plotted, projected and written like any other SpatVector.

Usage

# S4 method for SpatNetwork
shortestPath(x, from, to, ...)

Value

A SpatVector of lines with one feature per (from, to) pair, with columns

from: 1-based source node id
to: 1-based destination node id
distance: total path weight (NA if unreachable)

Arguments

x: SpatNetwork
from: integer. One or more 1-based node ids (rows of net_nodes(x)) to start from.
to: integer. One or more 1-based node ids to reach. Either from or to may be length 1 to be recycled against the other; otherwise the two must have the same length.
...: additional arguments (currently ignored)

Details

The implementation builds a single adjacency list from net_edges(x) and then runs one Dijkstra single-source shortest-path traversal per unique source node, caching the result so that querying many destinations from the same origin is efficient. Negative or NA edge weights are treated as zero (Dijkstra cannot handle negative cycles).

When a destination is unreachable from its source the corresponding output feature has an empty geometry and NA distance. When from == to the distance is 0 and the geometry is empty.

Examples

Run this code

# Two crossing roads
a <- vect("LINESTRING(0 0, 10 10)", crs = "local")
b <- vect("LINESTRING(0 10, 10 0)", crs = "local")
roads <- rbind(a, b)
roads$speed <- c(50, 100)   # km/h, used as a "cost" column

net <- netw(roads)
sp <- shortestPath(net, from = 1, to = 4)
sp$distance

# Multiple destinations from one source
shortestPath(net, from = 1, to = c(2, 3, 4, 5))$distance

# Custom weights from a column of the source SpatVector
nslow <- netw(roads, weights = "speed")
shortestPath(nslow, from = 1, to = 4)$distance