Skip to contents

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.

...

These dots are for future extensions and must be empty.

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 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.

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, 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.

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) doi: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(), reciprocity(), subcomponent(), subgraph(), topo_sort(), transitivity(), unfold_tree(), which_multiple(), which_mutual()

igraph_get_k_shortest_paths().