networkx不會放棄對加權圖

Question

所有最短路徑

我試圖找出所有可能的最短路徑

這裏是我的代碼：

import networkx as nx 
g=nx.Graph() 
e=[('a', 'b', 2), ('a', 'c', 6), ('b', 'c', 4), ('c', 'e', 5), ('c', 'f', 1)] 
paths=nx.shortest_paths(g,'a','c',weight=True) 
print('%s' %list(paths)) 

這裏是輸出：

[['a', 'c']] 

根據權重，a-> b-> c也是最短路徑。

爲什麼它沒有輸出？

Answer 1

而不是shortest_paths使用all_shortest_paths功能。

試試下面的代碼：

import networkx as nx 
g=nx.Graph() 
g.add_edge('a','b', distance=2) 
g.add_edge('a','c', distance=6) 
g.add_edge('b','c', distance=4) 
g.add_edge('c','e', distance=5) 
g.add_edge('c','f', distance=1) 
print([p for p in nx.all_shortest_paths(g,source='a',target='c',weight='distance')]) 

輸出：

[['a', 'c'], ['a', 'b', 'c']] 

Answer 2

我不能在我的筆記本電腦上運行代碼。

networkx-1.11 
Python 2.7.13 

所以我嘗試使用all_shortest_paths方法，也許在一定程度上他們是similar.Here是我的代碼：

import networkx as nx 

G = nx.Graph() 
e = [('a', 'b', 2), ('a', 'c', 6), ('b', 'c', 4)] 

for i in e: 
    G.add_edge(i[1], i[0], weight=i[2]) 


paths = nx.all_shortest_paths(G, source='a', target='c',weight=True) 

print list(paths) 

我得到了相同的輸出，和我讀networkx DOC約all_shortest_paths ：

• 重量

  （無或字符串，可選（默認=無）） - 如果沒有，每個 邊具有權重/距離/成本1.如果是字符串，則使用此邊屬性 作爲邊權重。任何邊緣屬性不存在默認爲1。

所以我想這weight=True是無效的，所以任何邊緣屬性不存在默認爲1，這就是爲什麼你不能得到你想要的結果。

如果您修改代碼並將weight=True更改爲weight='weight'。

您將獲得：

[['a', 'c'], ['a', 'b', 'c']] 

希望這有助於。