R/structural.properties.R
k_shortest_paths.RdFinds the \(k\) shortest paths between the given source and target vertex in order of increasing length. Currently this function uses Yen's algorithm.
k_shortest_paths(
graph,
from,
to,
...,
k,
weights = NULL,
mode = c("out", "in", "all", "total")
)The input graph.
The source vertex of the shortest paths.
The target vertex of the shortest paths.
These dots are for future extensions and must be empty.
The number of paths to find. They will be returned in order of increasing length.
Possibly a numeric vector giving edge weights. If this is
NULL and the graph has a weight edge attribute, then the
attribute is used. If this is NA then no weights are used (even if
the graph has a weight attribute). In a weighted graph, the length
of a path is the sum of the weights of its constituent edges.
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, if in then to
it will be considered. If all, the default, then the graph is treated
as undirected, i.e. edge directions are not taken into account. This
argument is ignored for undirected graphs.
A named list with two components is returned:
The list of \(k\) shortest paths in terms of vertices
The list of \(k\) shortest paths in terms of edges
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) doi:10.1090/qam/253822
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(),
reciprocity(),
subcomponent(),
subgraph(),
topo_sort(),
transitivity(),
unfold_tree(),
which_multiple(),
which_mutual()