如何检查igraph中两个顶点之间是否存在唯一的最短路径 [英] how to check if there exists a unique shortest path between two vertices in igraph

问题描述

我想用igraph识别两个顶点之间是否存在唯一的最短路径或多个最短路径.如果我使用length(all_shortest_paths(g, i,j)，这实际上对我有帮助，但是我觉得有很多多余的操作.我宁愿先使用get.shortest.paths(g, i,j)获得一条最短的路径，然后再查看是否存在另一条路径.但是，我不知道如何做到这一点.

I'd like to identify if there exist a unique shortest path or multiple shortest paths between two vertices with igraph. If I use length(all_shortest_paths(g, i,j), that actually helps me, but I feel like there are so many redundant operations. I rather prefer first to get one shortest path with get.shortest.paths(g, i,j), and then see if there is another. However, I could not figure out how to do this.

有人可以帮我确定是否存在与get.shortest.paths(g, i,j)获得的第一个最短路径不同的另一个最短路径吗?

Can someone help me how to identify whether there is another shortest path different than the first one obtained by get.shortest.paths(g, i,j)?

这是一个示例图

library(igraph)
data <- read.table(text="
1 2
1 4
1 5
2 3
2 4
3 4
5 7
5 8
3 6", header=FALSE)
gmatrix <- data.matrix(data, rownames.force = NA) #convert into a matrix to use in igraph
g <- graph_from_edgelist(gmatrix, directed = FALSE) 

例如，如果我想找到从1到3的最短路径，则使用all_shortest_paths(g, 1,3)，它会为我提供以下结果.

For instance, if I'd like to find the shortest path from 1 to 3, I use all_shortest_paths(g, 1,3), and it gives me the following result.

$res
$res[[1]]
+ 3/9 vertices, from 634c426:
[1] 1 4 3

$res[[2]]
+ 3/9 vertices, from 634c426:
[1] 1 2 3

我想要的是获得第一个最短的路径.例如

What I want is to get the first shortest path. For instance

get.shortest.paths(g, 1,3)
$vpath
$vpath[[1]]
+ 3/9 vertices, from 634c426:
[1] 1 2 3

现在，我想看看是否有与[1] 1 2 3不同的其他路径.在较大的图中，由于有数十种可能的最短路径，所以我不想使用all_shortest_paths(g, i,j)进行该查询.

Now, I want to see if there is any other path different than [1] 1 2 3. In a larger graph, since there are tens of possible shortest paths, I don't want to use all_shortest_paths(g, i,j) to make that query.

总的来说，我的问题是:如何检查两个顶点之间是否存在唯一的最短路径?我将给出两个顶点作为输入，作为回报，我应该得到TRUE或FALSE，以指示是否存在唯一的最短路径.

Overall, my question is: how can I check whether there exists a unique shortest path between two vertices or not? I will give two vertices as my input, in return I should get TRUE or FALSE indicating if there is a unique shortest path.

推荐答案

得到

After getting responded for How to assign edge weights to certain edges in R igraph, here is one solution. Please note that the initial network is an undirected graph with no edge weights.

p <- get.shortest.paths(g, i, j)$vpath[[1]] #shortest path between node i and node j
g <- set_edge_attr(g, "weight", value = ifelse(E(g) %in% E(g, path = p), 1.50, 1)) #Assign slightly larger edge weights to the edges existing in path p
q <- get.shortest.paths(g, i,j , weights = E(g)$weight)$vpath[[1]] #recalculate the shortest path with edge weights
g <- delete_edge_attr(g, "weight")
if(all(p %in% q))
#If paths p and q are the same, then the shortest path is unique

但是，由于运行时间长，这绝对不是一个好的解决方案.当我针对400个节点尝试此方法时，它需要几分钟才能停止.

However, this is definitely not a good solution due to the high running time. When I try this method for 400 nodes, it takes several minutes to stop.

这篇关于如何检查igraph中两个顶点之间是否存在唯一的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！