查找圖中兩個節點之間指定長度的所有可能路徑

Question

對於中等大小（~50個節點，平均度：〜4），無向圖未加權圖我想列舉指定長度之間的所有可能路徑兩個節點i和j使用R.

包igraph提供了all_simple_paths，我可以使用它，然後將結果簡單地分解爲我想要的長度的路徑。然而，問題在於all_simple_paths默認也列舉了所有可能的更長的路徑，即使對於相當小的網絡也需要數小時。

我知道在SO上有幾個非常類似的問題，但非專用於R，更重要的是不比igraph的all_simple_paths更近。

Answer 1

如果我正確理解你的問題，你不希望所有可能的路徑在i和j之間，而只是最短的 - 是嗎？

您可以使用igraph的all_shortest_paths函數來實現此功能。

考慮：

require(igraph) 
edges= graph.formula(A - B, 
        A - C, 
        B - C, 
        B - C, 
        C - D, 
        B - D, 
        D - E) 

如果我= A和j = d（隨便說）：

>all_shortest_paths(edges,from="A", to="D") 
$res 
$res[[1]] 
+ 3/5 vertices, named: 
[1] A C D 

$res[[2]] 
+ 3/5 vertices, named: 
[1] A B D 


$nrgeo 
[1] 1 1 1 2 0 

相反，all_simple_paths會給你更長的路徑（L = 4），我不想要：

> all_simple_paths(edges,from="A", to="D") 
[[1]] 
+ 4/5 vertices, named: 
[1] A B C D 

[[2]] 
+ 3/5 vertices, named: 
[1] A B D 

[[3]] 
+ 4/5 vertices, named: 
[1] A C B D 

[[4]] 
+ 3/5 vertices, named: 
[1] A C D 

我希望這有助於。