get_distance_pair: Compute shortest distance between origin and destination...

In cppRouting: Algorithms for Routing and Solving the Traffic Assignment Problem

Compute shortest distance between origin and destination nodes.

Description

Compute shortest distance between origin and destination nodes.

Usage

get_distance_pair(
  Graph,
  from,
  to,
  aggregate_aux = FALSE,
  algorithm = "bi",
  constant = 1,
  allcores = FALSE
)

Arguments

Graph	An object generated by makegraph, cpp_simplify or cpp_contract function.
from	A vector of one or more vertices from which distances are calculated (origin).
to	A vector of one or more vertices (destination).
aggregate_aux	Logical. If TRUE, the additional weight is summed along shortest paths.
algorithm	character. Dijkstra for uni-directional Dijkstra, bi for bi-directional Dijkstra, A* for A star unidirectional search or NBA for New bi-directional A star .Default to bi
constant	numeric. Constant to maintain the heuristic function admissible in A* and NBA algorithms. Default to 1, when cost is expressed in the same unit than coordinates. See details
allcores	Logical (deprecated). If TRUE, all cores are used.

Details

If graph is not contracted, the user has the choice between :

• unidirectional Dijkstra (Dijkstra)

• A star (A*) : projected coordinates should be provided

• bidirectional Dijkstra (bi)

• New bi-directional A star (NBA) : projected coordinates should be provided

If the input graph has been contracted by cpp_contract function, the algorithm is a modified bidirectional search.

Shortest path is always computed according to the main edge weights, corresponding to the 3rd column of df argument in makegraph function. If aggregate_aux argument is TRUE, the values returned are the sum of auxiliary weights along shortest paths.

In A* and New Bidirectional A star algorithms, euclidean distance is used as heuristic function.

All algorithms are multithreaded. allcores argument is deprecated, please use RcppParallel::setThreadOptions() to set the number of threads.

To understand how A star algorithm work, see https://en.wikipedia.org/wiki/A*_search_algorithm. To understand the importance of constant parameter, see the package description : https://github.com/vlarmet/cppRouting/blob/master/README.md

Value

Vector of shortest distances.

Note

from and to must be the same length. It is not possible to aggregate auxiliary weights on a Graph object coming from cpp_simplify function.

See Also

get_distance_matrix, get_path_pair, cpp_contract

Examples

#Choose number of cores used by cppRouting
RcppParallel::setThreadOptions(numThreads = 1)

#Data describing edges of the graph
edges<-data.frame(from_vertex=c(0,0,1,1,2,2,3,4,4),
                  to_vertex=c(1,3,2,4,4,5,1,3,5),
                  cost=c(9,2,11,3,5,12,4,1,6),
                  dist = c(5,3,4,7,5,5,5,8,7))

#Construct directed  graph with travel time as principal weight, and distance as secondary weight
graph <- makegraph(edges[,1:3], directed=TRUE, aux = edges$dist)

#Get all nodes IDs
nodes <- graph$dict$ref

# Get shortest times between all nodes : the result are in time unit
time_mat <- get_distance_pair(graph, from = nodes, to = nodes)

# Get distance according shortest times : the result are in distance unit
dist_mat <- get_distance_pair(graph, from = nodes, to = nodes, aggregate_aux = TRUE)

print(time_mat)
print(dist_mat)

cppRouting documentation built on Dec. 1, 2022, 5:08 p.m.