Find the k shortest paths between two vertices
Source:R/structural.properties.R
k_shortest_paths.Rd
Finds the k shortest paths between the given source and target vertex in order of increasing length. Currently this function uses Yen's algorithm.
Usage
k_shortest_paths(
graph,
from,
to,
...,
k,
weights = NULL,
mode = c("out", "in", "all", "total")
)
Arguments
- graph
The input graph.
- from
The source vertex of the shortest paths.
- to
The target vertex of the shortest paths.
- k
The number of paths to find. They will be returned in order of increasing length.
- weights
Possibly a numeric vector giving edge weights. If this is
NULL
and the graph has aweight
edge attribute, then the attribute is used. If this isNA
then no weights are used (even if the graph has aweight
attribute).- mode
Character constant, gives whether the shortest paths to or from the given vertices should be calculated for directed graphs. If
out
then the shortest paths from the vertex, ifin
then to it will be considered. Ifall
, the default, then the corresponding undirected graph will be used, i.e. not directed paths are searched. This argument is ignored for undirected graphs.
Value
A named list with two components is returned:
- vpaths
The list of k shortest paths in terms of vertices
- epaths
The list of k shortest paths in terms of edges
References
Yen, Jin Y.: An algorithm for finding shortest routes from all source nodes to a given destination in general networks. Quarterly of Applied Mathematics. 27 (4): 526–530. (1970) https://doi.org/10.1090/qam/253822
See also
shortest_paths()
, all_shortest_paths()
Other structural.properties:
bfs()
,
component_distribution()
,
connect()
,
constraint()
,
coreness()
,
degree()
,
dfs()
,
distance_table()
,
edge_density()
,
feedback_arc_set()
,
girth()
,
is_acyclic()
,
is_dag()
,
is_matching()
,
knn()
,
laplacian_matrix()
,
reciprocity()
,
subcomponent()
,
subgraph()
,
topo_sort()
,
transitivity()
,
unfold_tree()
,
which_multiple()
,
which_mutual()