最短路径函数 returns R igraph 中的错误路径
Shortest path function returns a wrong path in R igraph
我使用get.shortest.paths 方法找到两个顶点之间的最短路径。然而，奇怪的事情正在发生。在收到评论后，我正在更改整个问题正文。我用 g <- sample_smallworld(1, 20, 5, 0.1) 生成了我的图表，这是邻接列表。
*Vertices 20
*Edges
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 8 0
8 9 0
9 10 0
10 11 0
11 12 0
12 13 0
13 14 0
14 15 0
6 15 0
16 17 0
17 18 0
18 19 0
19 20 0
1 20 0
1 11 0
1 19 0
1 4 0
1 18 0
1 5 0
1 17 0
6 17 0
15 16 0
2 20 0
2 4 0
2 19 0
2 5 0
2 18 0
2 9 0
2 17 0
2 13 0
3 5 0
3 20 0
3 6 0
3 19 0
3 7 0
3 18 0
3 8 0
4 6 0
4 7 0
4 20 0
4 8 0
5 19 0
4 9 0
5 7 0
5 8 0
5 9 0
5 20 0
5 10 0
6 8 0
6 9 0
6 10 0
6 11 0
7 9 0
7 10 0
7 11 0
7 12 0
1 10 0
8 11 0
1 12 0
8 13 0
9 11 0
9 12 0
9 13 0
7 14 0
12 19 0
10 13 0
10 14 0
10 15 0
11 13 0
11 14 0
11 15 0
4 16 0
12 14 0
9 15 0
12 16 0
12 17 0
13 15 0
13 16 0
13 17 0
13 18 0
14 16 0
14 17 0
14 18 0
14 19 0
15 17 0
15 18 0
15 19 0
1 15 0
16 18 0
16 19 0
9 20 0
17 19 0
17 20 0
10 18 0
报告的 7 和 2 之间的最短路径是：
> get.shortest.paths(g,7,2)
$vpath
$vpath[[1]]
+ 4/20 vertices, from c915453:
[1] 7 14 19 2
这里是节点7和节点2的相邻节点：
> unlist(neighborhood(g, 1, 7, mode="out"))
[1] 7 3 4 5 6 8 9 10 11 12 14
> unlist(neighborhood(g, 1, 2, mode="out"))
[1] 2 1 3 4 5 9 13 17 18 19 20
如你所见，我可以从 7 到 3，从 3 到 2。看起来有更短的路径。我可能缺少什么？
是的，问题是你的边缘权重为零。查看帮助页面 ?shortest_paths
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).
请注意，weights=NULL 是默认值，因此将使用权重。因此，返回路径的权重为零 - 与您想要获得的路径相同。 weighted距离是一样的。如果你想找到跳数最少的路径，像这样关闭权重的使用：
get.shortest.paths(g,7,2, weights=NA)$vpath
我使用get.shortest.paths 方法找到两个顶点之间的最短路径。然而，奇怪的事情正在发生。在收到评论后，我正在更改整个问题正文。我用 g <- sample_smallworld(1, 20, 5, 0.1) 生成了我的图表，这是邻接列表。
*Vertices 20
*Edges
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 8 0
8 9 0
9 10 0
10 11 0
11 12 0
12 13 0
13 14 0
14 15 0
6 15 0
16 17 0
17 18 0
18 19 0
19 20 0
1 20 0
1 11 0
1 19 0
1 4 0
1 18 0
1 5 0
1 17 0
6 17 0
15 16 0
2 20 0
2 4 0
2 19 0
2 5 0
2 18 0
2 9 0
2 17 0
2 13 0
3 5 0
3 20 0
3 6 0
3 19 0
3 7 0
3 18 0
3 8 0
4 6 0
4 7 0
4 20 0
4 8 0
5 19 0
4 9 0
5 7 0
5 8 0
5 9 0
5 20 0
5 10 0
6 8 0
6 9 0
6 10 0
6 11 0
7 9 0
7 10 0
7 11 0
7 12 0
1 10 0
8 11 0
1 12 0
8 13 0
9 11 0
9 12 0
9 13 0
7 14 0
12 19 0
10 13 0
10 14 0
10 15 0
11 13 0
11 14 0
11 15 0
4 16 0
12 14 0
9 15 0
12 16 0
12 17 0
13 15 0
13 16 0
13 17 0
13 18 0
14 16 0
14 17 0
14 18 0
14 19 0
15 17 0
15 18 0
15 19 0
1 15 0
16 18 0
16 19 0
9 20 0
17 19 0
17 20 0
10 18 0
报告的 7 和 2 之间的最短路径是：
> get.shortest.paths(g,7,2)
$vpath
$vpath[[1]]
+ 4/20 vertices, from c915453:
[1] 7 14 19 2
这里是节点7和节点2的相邻节点：
> unlist(neighborhood(g, 1, 7, mode="out"))
[1] 7 3 4 5 6 8 9 10 11 12 14
> unlist(neighborhood(g, 1, 2, mode="out"))
[1] 2 1 3 4 5 9 13 17 18 19 20
如你所见，我可以从 7 到 3，从 3 到 2。看起来有更短的路径。我可能缺少什么？
是的，问题是你的边缘权重为零。查看帮助页面 ?shortest_paths
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).
请注意，weights=NULL 是默认值，因此将使用权重。因此，返回路径的权重为零 - 与您想要获得的路径相同。 weighted距离是一样的。如果你想找到跳数最少的路径，像这样关闭权重的使用：
get.shortest.paths(g,7,2, weights=NA)$vpath