R igraph 手册页

distance_table {igraph}

R 文档

顶点间最短（有向或无向）路径

描述

distances 计算网络中从顶点到顶点或从顶点到所有顶点的最短路径长度。shortest_paths 计算从给定顶点到顶点或从顶点到目标顶点的单条最短路径（路径本身，而不仅仅是其长度）。

用法

distance_table(graph, directed = TRUE)

mean_distance(
  graph,
  weights = NULL,
  directed = TRUE,
  unconnected = TRUE,
  details = FALSE
)

distances(
  graph,
  v = V(graph),
  to = V(graph),
  mode = c("all", "out", "in"),
  weights = NULL,
  algorithm = c("automatic", "unweighted", "dijkstra", "bellman-ford", "johnson")
)

shortest_paths(
  graph,
  from,
  to = V(graph),
  mode = c("out", "all", "in"),
  weights = NULL,
  output = c("vpath", "epath", "both"),
  predecessors = FALSE,
  inbound.edges = FALSE,
  algorithm = c("automatic", "unweighted", "dijkstra", "bellman-ford")
)

all_shortest_paths(
  graph,
  from,
  to = V(graph),
  mode = c("out", "all", "in"),
  weights = NULL
)

参数

图	要操作的图。
有向	是否考虑有向图中的有向路径，此参数对于无向图将被忽略。
weights	可能是一个数字向量，给出边的权重。如果这是 NULL 并且图具有 weight 边属性，则使用该属性。 如果这是 NA，则不使用权重（即使图具有 weight 属性）。
unconnected	如果图未连接（如果考虑有向路径则非强连接），该怎么办。 如果为 TRUE，则仅考虑现有路径的长度并进行平均；如果为 FALSE，则缺失路径的长度被视为具有无限长度，这也使得平均距离为无穷大。
详情	是否在结果中提供其他详细信息。 接受此参数的函数（如 mean_distance）在将此参数设置为 TRUE 时，会在结果中返回其他信息，例如断开连接的顶点对的数量。
v	数字向量，将计算最短路径的顶点。
到	数字向量，将计算最短路径的目标顶点。 默认情况下，它包括所有顶点。 请注意，对于 distances，每个顶点在此处最多只能包含一次。 （shortest_paths 不需要此设置）。
模式	字符常量，指示对于有向图，应计算到给定顶点的最短路径还是从给定顶点计算最短路径。 如果为 out，则考虑从顶点的最短路径；如果为 in，则考虑到顶点的最短路径。 如果为 all（默认设置），则将使用相应的无向图，即搜索非有向路径。 此参数对于无向图将被忽略。
algorithm	用于计算的算法。 默认情况下，igraph 尝试选择最快的合适算法。 如果没有权重，则使用未加权广度优先搜索；否则，如果所有权重均为正数，则使用 Dijkstra 算法。 如果存在负权重并且我们为 100 多个源执行计算，则使用 Johnson 算法。 否则，使用 Bellman-Ford 算法。 您可以通过显式提供此参数来覆盖 igraph 的选择。 请注意，igraph C 核心可能仍然会在明显的情况下覆盖您的选择，即，如果没有边权重，则无论此参数如何，都将使用未加权算法。
从	数字常量，将计算到最短路径的顶点或从中计算最短路径的顶点。 请注意，现在这不是顶点 ID 的向量，而只是单个顶点。
输出	字符标量，定义如何报告最短路径。“vpath” 表示报告沿路径的顶点，此形式在 igraph 版本 0.6 之前使用。“epath” 表示报告沿路径的边。“both” 表示返回两种形式，在具有“vpath”和“epath”组件的命名列表中。
前任	逻辑标量，指示是否为每个顶点返回前驱顶点。 树中顶点 i 的前驱是从中到达顶点 i 的顶点。 根据定义，起始顶点（在 from 参数中）的前驱是它本身。 如果前驱为零，则表示在搜索期间未从源到达给定顶点。 请注意，如果到达 to 中的所有顶点，则搜索终止。
inbound.edges	逻辑标量，指示是否为每个顶点返回入站边。 树中顶点 i 的入站边是顶点 i 通过其到达的边。 起始顶点和在搜索期间未到达的顶点将在向量的相应条目中显示零。 请注意，如果到达 to 中的所有顶点，则搜索终止。

详细信息

两个顶点对之间的最短路径或测地线是具有最少顶点数的路径。 本手册页中记录的函数都计算顶点对之间的最短路径。

distances 计算从一组顶点 (from) 到另一组顶点 (to) 的成对最短路径的长度。 它使用不同的算法，具体取决于 algorithm 参数和图的 weight 边属性。 实现的算法是广度优先搜索 (‘unweighted’)，它仅适用于未加权图；Dijkstra 算法 (‘dijkstra’)，它适用于具有非负边权重的图；Bellman-Ford 算法 (‘bellman-ford’) 和 Johnson 算法 (‘"johnson"’)。 后两种算法适用于任意边权重，但（自然地）仅适用于没有负循环的图。

igraph 可以在算法之间自动选择，并选择最适合提供的权重（如果有）的算法。 对于自动算法选择，请提供 ‘automatic’ 作为 algorithm 参数。 （这也是默认设置。）

shortest_paths 计算从 from 中给定的源顶点到 to 中给定的目标顶点之间的单条最短路径（即路径本身，而不仅仅是其长度）。 shortest_paths 对未加权图使用广度优先搜索，对加权图使用 Dijkstra 算法。 后者仅在边权重为非负数时有效。

all_shortest_paths 计算顶点对之间的所有最短路径。 更准确地说，是从 from 顶点到 to 中给定的顶点的最短路径。 它对未加权图使用广度优先搜索，对加权图使用 Dijkstra 算法。 后者仅支持非负边权重。

mean_distance 通过计算所有顶点对之间的最短路径（对于有向图，两个方向都计算）来计算图中的平均路径长度。 它对未加权图使用广度优先搜索，对加权图使用 Dijkstra 算法。 后者仅支持非负边权重。

distance_table 通过计算每对顶点之间的最短路径长度来计算直方图。 对于有向图，两个方向都考虑在内，因此每对顶点在直方图中出现两次。

值

对于 distances，是一个数字矩阵，具有 length(to) 列和 length(v) 行。 从顶点到其自身的最短路径长度始终为零。 对于无法到达的顶点，包含 Inf。

对于 shortest_paths，返回一个具有四个条目的命名列表

vpath	它本身是一个列表，长度为 length(to)； 列表元素 i 包含从顶点 from 到顶点 to[i] 的路径（或者对于有向图，取决于 mode 参数，反之亦然）上的顶点 ID。 该向量还包含 from 和 i 作为第一个和最后一个元素。 如果 from 与 i 相同，则仅包含一次。 如果两个顶点之间没有路径，则返回长度为零的数字向量作为列表元素。 如果 output 参数中未请求此输出，则它将为 NULL。
epath	这是一个类似于 vpath 的列表，但列表的向量包含沿最短路径的边 ID，而不是顶点 ID。 如果在 output 参数中未请求此条目，则此条目设置为 NULL。
前任	数字向量，to 参数中每个顶点的前驱，如果未请求，则为 NULL。
inbound_edges	数字向量，每个顶点的入站边，如果未请求，则为 NULL。

对于 all_shortest_paths，返回一个列表，每个列表元素包含从 from 到 to 中的顶点的最短路径。 到达同一顶点的最短路径被收集到列表的连续元素中。

对于 mean_distance，如果 details=FALSE，则返回一个数字；或者返回一个具有两个条目的命名列表：res 是平均距离（作为数字标量），unconnected 是未连接的顶点对的数量（也作为数字标量）。

distance_table 返回一个具有两个条目的命名列表：res 是数字向量，即距离的直方图，unconnected 是数字标量，即第一个顶点无法从第二个顶点到达的对的数量。 对于有向图，两个条目的总和始终为 n(n-1)，对于无向图，总和始终为 n(n-1)/2。

作者

Gabor Csardi csardi.gabor@gmail.com

参考

West, D.B. (1996). 图论导论。 Upper Saddle River, N.J.: Prentice Hall.

示例

g <- make_ring(10)
distances(g)
shortest_paths(g, 5)
all_shortest_paths(g, 1, 6:8)
mean_distance(g)
## Weighted shortest paths
el <- matrix(ncol=3, byrow=TRUE,
             c(1,2,0, 1,3,2, 1,4,1, 2,3,0, 2,5,5, 2,6,2, 3,2,1, 3,4,1,
               3,7,1, 4,3,0, 4,7,2, 5,6,2, 5,8,8, 6,3,2, 6,7,1, 6,9,1,
               6,10,3, 8,6,1, 8,9,1, 9,10,4) )
g2 <- add_edges(make_empty_graph(10), t(el[,1:2]), weight=el[,3])
distances(g2, mode="out")

---