最短路徑搜索 - 使用邊緣類型[NetworkX，igraph]

Question

我使用Directed MultiGraph作爲數據結構（兩個節點之間可能多於一個邊緣）。

我想分配我的MultiDiGraph不同類型的邊緣。例如，邊（u，v_1）可以是type_1，另一個邊（u，v_2）可以是類型2.

構建此數據結構後，我希望找到最短路徑，但路徑必須僅包含邊某些類型（例如，類型1）。在NetworkX或python-igraph庫中可能嗎？

Answer 1

正如網絡x中的@Gabor Csardi所建議的那樣，要添加類型1的邊：將屬性type_1添加到所需的值，並將屬性type_2添加到最大值int（在最短路徑計算中忽略，就好像它不存在）。同樣，執行同樣的操作來創建type_2的邊緣。

下面的代碼顯示了一個簡單的圖表，其中從1到4的最短路徑在type_1邊緣中短於2，在type_2邊緣中短於3。

g=nx.MultiDiGraph() 
g.add_edge(1,2,type1=2,type2=sys.maxint) # add edge of type 1 
g.add_edge(1,2,type1=sys.maxint,type2=3) # add edge of type 2 
g.add_edge(2,4,type1=2,type2=sys.maxint) 
g.add_edge(2,4,type1=sys.maxint,type2=4) 
g.add_edge(3,4,type1=3,edge_type2=sys.maxint) 
g.add_edge(3,4,type1=sys.maxint,type2=1) 
g.add_edge(1,3,type1=sys.maxint,type2=1) 
print nx.shortest_path(g,1,4,weight='type1') 
print nx.shortest_path(g,1,4,weight='type2') 

結果：

[1, 2, 4] 
[1, 3, 4] 

另外，附上所創建的圖表能夠想象它更容易。