k_shortest_paths: Find the k shortest paths between two vertices

In igraph: Network Analysis and Visualization

Find the k shortest paths between two vertices

Description

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

Related documentation in the C library

igraph_get_k_shortest_paths().

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) \Sexpr[results=rd]{tools:::Rd_expr_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 documentation built on Oct. 20, 2024, 1:06 a.m.