Shortest paths through a network

Mirrors the C# Dijkstra.Solve overloads: solves the cheapest route from EVERY node of a directed, weighted graph to a set of destination nodes at once, running the search backwards from the destinations. The answer is a routing table – for each node, which neighbour to step to, along which edge, and at what remaining cost.

Usage

shortest_path(
  from,
  to,
  weight,
  destinations,
  edge_index = NULL,
  node_count = NULL
)

Arguments

from, to, weight

numeric vectors of the same length, one element per directed edge: the start node index, the end node index, and the cost of traversing the edge. from and to must be whole, non-negative numbers.

destinations

a numeric vector of one or more destination node indices. With several destinations, each node keeps whichever destination it reaches most cheaply.

edge_index

an optional numeric vector the same length as from, labelling each edge (typically an index into whatever the edges came from – a river reach, a road segment). Defaults to 0:(length(from) - 1). These labels are what the edge_index result column reports, and they need not be distinct.

node_count

an optional node count. Defaults to max(from, to) + 1; supply a larger value to include isolated nodes carrying no edge, which then report cost = Inf. A value below max(from, to) + 1 is an error: the graph would not fit the routing table it asks for.

Value

a data frame with one row per node, in node-index order, and columns next_node, edge_index (both integer) and cost (numeric).

Details

Node indices are 0-based in both corehydror and corehydropy, matching the C# result table the two packages share; a graph with n nodes uses indices 0 to n - 1. Unreachable nodes carry cost = Inf with next_node = -1 and edge_index = -1, and a destination node carries cost = 0 with next_node equal to its own index.

Costs accumulate in single precision, because the ported solver does (C# declares float Weight and its own tests assert the table by exact float equality). Fractional weights therefore round to float before they are summed.

Examples

# 0 -> 1 -> 2, plus a disconnected node 3
shortest_path(
  from = c(0, 1),
  to = c(1, 2),
  weight = c(1, 1),
  destinations = 2,
  node_count = 4
)
#>   next_node edge_index cost
#> 1         1          0    2
#> 2         2          1    1
#> 3         2         -1    0
#> 4        -1         -1  Inf