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",
"floyd-warshall")
)
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
)参数
- graph
要操作的图。
- directed
是否在有向图中考虑有向路径，此参数对于无向图将被忽略。
- weights
可能是一个数值向量，给出边的权重。如果这是
NULL并且图具有weight边属性，则使用该属性。如果这是NA，则不使用权重（即使图具有weight属性）。在加权图中，路径的长度是其组成边的权重之和。- unconnected
如果图未连接（如果考虑有向路径，则不是强连接），该怎么办。如果为 TRUE，则仅考虑现有路径的长度并取平均值；如果为 FALSE，则将缺失路径的长度视为具有无限长度，从而使平均距离也变为无限。
- details
是否在结果中提供更多详细信息。接受此参数的函数（例如
mean_distance()）会在将此参数设置为TRUE时返回其他信息，例如断开连接的顶点对的数量。- v
数值向量，将从中计算最短路径的顶点。
- to
数值向量，将计算最短路径到达的顶点。默认情况下，它包括所有顶点。请注意，对于
distances()，每个顶点最多只能在此处包含一次。（shortest_paths()不需要这样做。）- mode
字符常量，给出对于有向图，应计算到给定顶点的最短路径还是从给定顶点计算最短路径。如果为
out，则考虑从顶点的最短路径，如果为in，则考虑到顶点的最短路径。如果为all（默认值），则将图视为无向图，即不考虑边的方向。此参数对于无向图将被忽略。- algorithm
用于计算的算法。默认情况下，igraph 尝试选择最快的适用算法。如果没有权重，则使用未加权广度优先搜索；否则，如果所有权重均为正，则使用 Dijkstra 算法。如果有负权重，并且我们对超过 100 个源执行计算，则使用 Johnson 算法。否则，使用 Bellman-Ford 算法。您可以通过显式给出此参数来覆盖 igraph 的选择。请注意，igraph C 核心可能仍然会在明显的情况下覆盖您的选择，即，如果没有边权重，则无论此参数如何，都将使用未加权算法。
- from
数值常量，将从中或到此计算最短路径的顶点。请注意，现在这不是顶点 ID 的向量，而只是单个顶点。
- output
字符标量，定义如何报告最短路径。“vpath”表示报告路径上的顶点，此形式在 igraph 版本 0.6 之前使用。“epath”表示报告路径上的边。“both”表示返回两种形式，在一个名为 “vpath” 和 “epath” 的命名列表中。
- predecessors
逻辑标量，是否为每个顶点返回前驱顶点。树中顶点
i的前驱是从顶点i到达的顶点。根据定义，起始顶点（在from参数中）的前驱是其本身。如果前驱为零，则表示在搜索期间未从源到达给定顶点。请注意，如果到达to中的所有顶点，则搜索将终止。- inbound.edges
逻辑标量，是否为每个顶点返回入边。树中顶点
i的入边是通过其到达顶点i的边。起始顶点和在搜索期间未到达的顶点将在向量的相应条目中为零。请注意，如果到达to中的所有顶点，则搜索将终止。
值
对于 distances()，一个数值矩阵，具有 length(to) 列和 length(v) 行。从顶点到其自身的最短路径长度始终为零。对于无法到达的顶点，包含 Inf。
对于 shortest_paths()，返回一个具有四个条目的命名列表
- vpath
这本身是一个列表，长度为
length(to)；列表元素i包含从顶点from到顶点to[i]的路径上的顶点 ID（或对于有向图，根据mode参数，反之亦然）。该向量还包含from和i作为第一个和最后一个元素。如果from与i相同，则仅包含一次。如果两个顶点之间没有路径，则返回长度为零的数值向量作为列表元素。如果未在output参数中请求此输出，则它将为NULL。- epath
这是一个类似于
vpath的列表，但是列表的向量包含最短路径上的边 ID，而不是顶点 ID。如果在output参数中未请求此条目，则将其设置为NULL。- predecessors
数值向量，
to参数中每个顶点的前驱，如果未请求则为NULL。- inbound_edges
数值向量，每个顶点的入边，如果未请求则为
NULL。
对于 all_shortest_paths()，返回一个列表
- vpaths
这是一个列表。每个列表元素包含从
from到to中某个顶点的最短路径的顶点。到同一顶点的最短路径被收集到列表的连续元素中。- epaths
这是一个类似于 vpaths 的列表，但是列表的向量包含最短路径上的边 ID，而不是顶点 ID。
- nrgeo
一个向量，其中每个元素是从
from到to中相应顶点的最短路径（测地线）的数量。- res
已弃用
对于 mean_distance()，如果 details=FALSE，则返回单个数字；或者返回一个具有两个条目的命名列表
res平均距离作为数值标量
unconnected未连接的顶点对的数量，也作为数值标量。
distance_table() 返回一个具有两个条目的命名列表
res数值向量，距离的直方图
unconnected数值标量，第一个顶点无法从第二个顶点到达的对的数量。在无向图和有向图中，分别考虑无序对和有序对。因此，对于有向图，两个条目的总和始终为 \(n(n-1)\)，对于无向图，总和始终为 \(n(n-1)/2\)。
详细信息
两个顶点对之间的最短路径或测地线是具有最小顶点数的路径。此手册页中记录的函数都计算顶点对之间的最短路径。
distances() 计算从一组顶点 (from) 到另一组顶点 (to) 的成对最短路径的长度。它使用不同的算法，具体取决于 algorithm 参数和图的 weight 边属性。实现的算法是广度优先搜索（“unweighted”），这仅适用于未加权图；Dijkstra 算法（“dijkstra”），这适用于具有非负边权重的图；Bellman-Ford 算法（“bellman-ford”）；Johnson 算法（“johnson”）；以及 Floyd-Warshall 算法的更快版本，具有预期的二次运行时间（“floyd-warshall”）。后三种算法适用于任意边权重，但（自然地）仅适用于没有负循环的图。请注意，无向图中的负权重边意味着存在这样的循环。当给出许多源（和目标）顶点时，Johnson 算法比 Bellman-Ford 算法表现更好，全对最短路径长度计算是典型的用例。
igraph 可以在算法之间自动选择，并选择最适合提供的权重（如果有）的最有效算法。对于自动算法选择，请提供“automatic”作为 algorithm 参数。（这也是默认值。）
shortest_paths() 计算源顶点（在 from 中给出）到目标顶点（在 to 中给出）之间的单个最短路径（即路径本身，而不仅仅是其长度）。shortest_paths() 对未加权图使用广度优先搜索，对加权图使用 Dijkstra 算法。后者仅在边权重为非负数时才有效。
all_shortest_paths() 计算顶点对之间的所有最短路径，包括多个相同长度的最短路径。更准确地说，它计算从 from 开始并以 to 中给出的任何顶点结束的所有最短路径。它对未加权图使用广度优先搜索，对加权图使用 Dijkstra 算法。后者仅支持非负边权重。注意：在多重图中，结果大小与顶点对的数量呈指数关系，顶点对之间存在多条边。
mean_distance() 通过计算所有顶点对之间的最短路径（对于有向图，两个方向都计算），计算图中的平均路径长度。它对未加权图使用广度优先搜索，对加权图使用 Dijkstra 算法。后者仅支持非负边权重。
distance_table() 通过计算每对顶点之间的最短路径长度来计算直方图。对于有向图，两个方向都被考虑在内，因此每对顶点在直方图中出现两次。
参见
其他 structural.properties: bfs(), component_distribution(), connect(), constraint(), coreness(), degree(), dfs(), edge_density(), feedback_arc_set(), feedback_vertex_set(), girth(), is_acyclic(), is_dag(), is_matching(), k_shortest_paths(), knn(), reciprocity(), subcomponent(), subgraph(), topo_sort(), transitivity(), unfold_tree(), which_multiple(), which_mutual()
其他路径: all_simple_paths(), diameter(), eccentricity(), graph_center(), radius()
作者
Gabor Csardi csardi.gabor@gmail.com
示例
g <- make_ring(10)
distances(g)
#> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,] 0 1 2 3 4 5 4 3 2 1
#> [2,] 1 0 1 2 3 4 5 4 3 2
#> [3,] 2 1 0 1 2 3 4 5 4 3
#> [4,] 3 2 1 0 1 2 3 4 5 4
#> [5,] 4 3 2 1 0 1 2 3 4 5
#> [6,] 5 4 3 2 1 0 1 2 3 4
#> [7,] 4 5 4 3 2 1 0 1 2 3
#> [8,] 3 4 5 4 3 2 1 0 1 2
#> [9,] 2 3 4 5 4 3 2 1 0 1
#> [10,] 1 2 3 4 5 4 3 2 1 0
shortest_paths(g, 5)
#> $vpath
#> $vpath[[1]]
#> + 5/10 vertices, from 64a49d2:
#> [1] 5 4 3 2 1
#>
#> $vpath[[2]]
#> + 4/10 vertices, from 64a49d2:
#> [1] 5 4 3 2
#>
#> $vpath[[3]]
#> + 3/10 vertices, from 64a49d2:
#> [1] 5 4 3
#>
#> $vpath[[4]]
#> + 2/10 vertices, from 64a49d2:
#> [1] 5 4
#>
#> $vpath[[5]]
#> + 1/10 vertex, from 64a49d2:
#> [1] 5
#>
#> $vpath[[6]]
#> + 2/10 vertices, from 64a49d2:
#> [1] 5 6
#>
#> $vpath[[7]]
#> + 3/10 vertices, from 64a49d2:
#> [1] 5 6 7
#>
#> $vpath[[8]]
#> + 4/10 vertices, from 64a49d2:
#> [1] 5 6 7 8
#>
#> $vpath[[9]]
#> + 5/10 vertices, from 64a49d2:
#> [1] 5 6 7 8 9
#>
#> $vpath[[10]]
#> + 6/10 vertices, from 64a49d2:
#> [1] 5 4 3 2 1 10
#>
#>
#> $epath
#> NULL
#>
#> $predecessors
#> NULL
#>
#> $inbound_edges
#> NULL
#>
all_shortest_paths(g, 1, 6:8)
#> $vpaths
#> $vpaths[[1]]
#> + 6/10 vertices, from 64a49d2:
#> [1] 1 10 9 8 7 6
#>
#> $vpaths[[2]]
#> + 6/10 vertices, from 64a49d2:
#> [1] 1 2 3 4 5 6
#>
#> $vpaths[[3]]
#> + 5/10 vertices, from 64a49d2:
#> [1] 1 10 9 8 7
#>
#> $vpaths[[4]]
#> + 4/10 vertices, from 64a49d2:
#> [1] 1 10 9 8
#>
#>
#> $epaths
#> $epaths[[1]]
#> [1] 10 9 8 7 6
#>
#> $epaths[[2]]
#> [1] 1 2 3 4 5
#>
#> $epaths[[3]]
#> [1] 10 9 8 7
#>
#> $epaths[[4]]
#> [1] 10 9 8
#>
#>
#> $nrgeo
#> [1] 1 1 1 1 1 2 1 1 1 1
#>
#> $res
#> $res[[1]]
#> + 6/10 vertices, from 64a49d2:
#> [1] 1 10 9 8 7 6
#>
#> $res[[2]]
#> + 6/10 vertices, from 64a49d2:
#> [1] 1 2 3 4 5 6
#>
#> $res[[3]]
#> + 5/10 vertices, from 64a49d2:
#> [1] 1 10 9 8 7
#>
#> $res[[4]]
#> + 4/10 vertices, from 64a49d2:
#> [1] 1 10 9 8
#>
#>
mean_distance(g)
#> [1] 2.777778
## 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")
#> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,] 0 0 0 1 5 2 1 13 3 5
#> [2,] Inf 0 0 1 5 2 1 13 3 5
#> [3,] Inf 1 0 1 6 3 1 14 4 6
#> [4,] Inf 1 0 0 6 3 1 14 4 6
#> [5,] Inf 5 4 5 0 2 3 8 3 5
#> [6,] Inf 3 2 3 8 0 1 16 1 3
#> [7,] Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf
#> [8,] Inf 4 3 4 9 1 2 0 1 4
#> [9,] Inf Inf Inf Inf Inf Inf Inf Inf 0 4
#> [10,] Inf Inf Inf Inf Inf Inf Inf Inf Inf 0