跳到内容

查找两个顶点之间的\(k\)条最短路径

来源：R/structural-properties.R
k_shortest_paths.Rd

按长度递增的顺序查找给定源顶点和目标顶点之间的\(k\)条最短路径。目前，此函数使用 Yen 算法。

用法

k_shortest_paths(
  graph,
  from,
  to,
  ...,
  k,
  weights = NULL,
  mode = c("out", "in", "all", "total")
)

参数

graph

输入图。

from

最短路径的源顶点。

to

最短路径的目标顶点。

...

这些点用于未来的扩展，并且必须为空。

k

要查找的路径数。它们将按长度递增的顺序返回。

weights

可能是一个数值向量，给出边的权重。如果这是NULL，并且图具有 weight 边属性，则使用该属性。如果这是 NA，则不使用权重（即使图具有 weight 属性）。在加权图中，路径的长度是其组成边的权重之和。

mode

字符常量，指示对于有向图，应计算到给定顶点或从给定顶点出发的最短路径。如果为 out，则考虑从顶点出发的最短路径；如果为 in，则考虑到顶点的最短路径。如果为 all（默认值），则将图视为无向图，即不考虑边的方向。此参数对于无向图将被忽略。

值

返回一个具有两个组件的命名列表

vpaths

以顶点表示的 \(k\) 条最短路径的列表

epaths

以边表示的 \(k\) 条最短路径的列表

参考文献

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()

其他 structural.properties: bfs(), component_distribution(), connect(), constraint(), coreness(), degree(), dfs(), distance_table(), edge_density(), feedback_arc_set(), feedback_vertex_set(), girth(), is_acyclic(), is_dag(), is_matching(), knn(), reciprocity(), subcomponent(), subgraph(), topo_sort(), transitivity(), unfold_tree(), which_multiple(), which_mutual()

get_k_shortest_paths().