问题

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

python - 带有标记边的图形中的最短路径-LMLPHP

到目前为止我有什么

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)?

最佳答案

您可以将边缘转换为节点,并使用功能all_shortest_paths()

import networkx as nx

G = 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 nodes
g = 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']]

关于python - 带有标记边的图形中的最短路径,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/57819536/

10-11 23:00