基于边的两个节点之间的所有路径

Question

我的问题是关于所有简单路径的问题，感觉就像在做梦一样。我需要找到两个节点之间的所有路径，这个是基于边而不是节点来寻找的。

我找到了这个作为解决方案，但考虑到我实际图的大小，这种方法实在是太慢了。我想知道有什么优化可以做得更好。我已经修改了链接中的代码，使用了deque()。

这个也没有太大帮助

  g=nx.MultiGraph()
  g.add_edge(1,1,key='a')
  g.add_edge(1,2,key='b')
  g.add_edge(2,4,key='c')
  g.add_edge(2,4,key='d')
  g.add_edge(3,2,key='e')
  g.add_edge(3,3,key='f')
  g.add_edge(1,3,key='g')
  g.add_edge(1,5,key='h')
  g.add_edge(5,5,key='i')

对于all_path(1,4)的答案是：

Path: 0 --> [(1, 1, 'a'), (1, 2, 'b'), (2, 4, 'c')]
Path: 1 --> [(1, 1, 'a'), (1, 2, 'b'), (2, 4, 'd')]
Path: 2 --> [(1, 1, 'a'), (1, 3, 'g'), (3, 2, 'e'), (2, 4, 'c')]
Path: 3 --> [(1, 1, 'a'), (1, 3, 'g'), (3, 2, 'e'), (2, 4, 'd')]
Path: 4 --> [(1, 1, 'a'), (1, 3, 'g'), (3, 3, 'f'), (3, 2, 'e'), (2, 4, 'c')]
Path: 5 --> [(1, 1, 'a'), (1, 3, 'g'), (3, 3, 'f'), (3, 2, 'e'), (2, 4, 'd')]
Path: 6 --> [(1, 2, 'b'), (2, 4, 'c')]
Path: 7 --> [(1, 2, 'b'), (2, 4, 'd')]
Path: 8 --> [(1, 3, 'g'), (3, 2, 'e'), (2, 4, 'c')]
Path: 9 --> [(1, 3, 'g'), (3, 2, 'e'), (2, 4, 'd')]
Path: 10 --> [(1, 3, 'g'), (3, 3, 'f'), (3, 2, 'e'), (2, 4, 'c')]
Path: 11 --> [(1, 3, 'g'), (3, 3, 'f'), (3, 2, 'e'), (2, 4, 'd')]

Answer 1

试着构建一个新的图，把当前的边变成节点。如果两个节点之间有边，说明我们可以在路径中连续使用它们对应的边。完成这个后，你就可以用深度优先搜索（DFS）来解决你的问题。