图中带有标记边的最短路径

Question

问题

假设我有一个带有标记节点和边的图（见图）。我的目标是获得A 和 D 之间所有最短路径的集合。

到目前为止我所拥有的

import networkx as nx

G = nx.Graph()

G.add_edge('A', 'B')

G.add_edge('B', 'D')

G.add_edge('B', 'C')

shortest_path = nx.shortest_path(G, 'A', 'D')

在shortest_path我得到['A', 'B', 'D']. 当然，这是通过节点表示的最短路径，但我需要的是：

1）在我的图表中添加边缘标签

2）找到所有可能的最短路径的集合。理想情况下，shortest_paths我希望得到如下输出： [ A -> a -> B, B -> b -> D], [A -> a -> B, B -> c -> D]

问题

1）这可以用networkx来完成吗？

2）如果不是，还有哪些其他图形库包含解决这种场景问题的函数（不一定是 Python）？

Answer 1

您可以将边缘转换为节点并使用以下功能all_shortest_paths()：import networkx as nxG = nx.MultiGraph()G.add_edge('A', 'B', label='a')G.add_edge('B', 'D', label='b')G.add_edge('B', 'D', label='c')G.add_edge('B', 'C', label='d')G.add_edge('C', 'D', label='e')# Convert edges to nodesg = nx.Graph()for i, j, label in G.edges(data='label'):    g.add_edge(i, label)    g.add_edge(j, label)print(list(nx.all_shortest_paths(g, 'A', 'D')))# [['A', 'a', 'B', 'b', 'D'], ['A', 'a', 'B', 'c', 'D']]