30秒到達戰(zhàn)場
2022-05-19 19:02:09
問題假設我有一個帶有標記節(jié)點和邊的圖(見圖)。我的目標是獲得A 和 D 之間所有最短路徑的集合。到目前為止我所擁有的import networkx as nxG = 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']. 當然,這是通過節(jié)點表示的最短路徑,但我需要的是:1)在我的圖表中添加邊緣標簽2)找到所有可能的最短路徑的集合。理想情況下,shortest_paths我希望得到如下輸出: [ A -> a -> B, B -> b -> D], [A -> a -> B, B -> c -> D]問題1)這可以用networkx來完成嗎?2)如果不是,還有哪些其他圖形庫包含解決這種場景問題的函數(shù)(不一定是 Python)?
1 回答

犯罪嫌疑人X
TA貢獻2080條經(jīng)驗 獲得超4個贊
您可以將邊緣轉換為節(jié)點并使用以下功能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']]
添加回答
舉報
0/150
提交
取消