python - 最短路径搜索 - 使用边类型 [NetworkX、igraph]

Question

我使用有向多图作为数据结构(两个节点之间可能有多个边)。

我想在我的 MultiDiGraph 中分配不同类型的边。例如，边(u,v_1)可以是类型_1，另一条边(u,v_2)可以是类型2。

构建此数据结构后，我想找到最短路径，但路径必须仅包含某种类型的边(例如类型 1)。 NetworkX 或 python-igraph 库中可能吗？

Answer 1

按照@Gabor Csardi在networkx中的建议，要添加类型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')

The result:

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

此外，请找到附件中创建的图表，以便能够更轻松地对其进行可视化。