最短路径搜索 - 使用边缘类型[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] 

另外，附上所创建的图表能够想象它更容易。