帶有networkx的加權圖的所有最短路徑？

我有一個由兩組不同的邊組成的圖。第一組是由權重1（列表1）的邊緣製成的。第二組由權重2（列表2）的邊緣構成。首先，我使用networkx創建圖形，然後使用add_edges_from添加列表1和列表2.我想計算此加權圖形中的所有最短路徑。基本上，我正在尋找類似於「all_shortest_paths」的權重（看起來像「dijkstra」模塊不允許你知道給定源和給定目標之間的所有可能路線）。如果我嘗試使用加權鏈接（3元組，兩個節點和權重）的「all_shortest_path」，我會得到錯誤。有誰能夠幫助我？非常感謝！帶有networkx的加權圖的所有最短路徑？

來源

2013-05-14 user2382948

我注意到，我的解釋是完全不清楚，對不起。管理員可能想刪除以前的評論（沒有問題，這是我的不好）。基本上我有這個，edge_W1是行列表（每行有3個入口，兩個節點和1個連接它們的鏈接的權重）W = nx.Graph（）W.add_weighted_edges_from（edges_W1）。如果我打印nx.all_shortest_paths（W，0,1），我得到「發生器對象all_shortest_paths在<>。0和1之間的0x9b8ed9c當然只是一個例子 – user2382948

下面是一個簡單的例子來說明all_shortest_paths（）是如何工作的

import networkx as nx 
import StringIO 
edges = StringIO.StringIO(""" 
a b 1 
a bb 1 
b c 2 
bb c 2 
c d 1 
a d 10""") 
G = nx.read_weighted_edgelist(edges, nodetype=str) 
print list(nx.all_shortest_paths(G, 'a', 'd', weight='weight')) 
# [['a', 'b', 'c', 'd'], ['a', 'bb', 'c', 'd']]

來源

2013-05-16 01:48:18 Aric

親愛的阿里克，非常感謝你的幫助！ – user2382948

僅供參考， ''nx.all_shortest_paths''使用dijkstra方法來獲得每個頂點的''pred''和''dist''，所以如果圖形包含負加權邊緣，則不會給出正確的結果。 – Dzhuang

帶有networkx的加權圖的所有最短路徑？

回答

相關問題