Python：最短加權路徑和最少邊數

我正在使用networkx加權圖來建模交通網絡。我試圖根據加權邊的總和來找到最短路徑。我用Dijkstra路徑來找到這條路。我的問題發生在加權邊緣方面。當發生這種情況時，我總是希望從綁定的路徑集合中選擇具有最少邊數的路徑。 Dijkstra路徑似乎沒有這樣做。Python：最短加權路徑和最少邊數

有沒有一種方法可以確保我可以從一組路徑中選擇具有最少邊數的路徑，這些路徑根據加權邊的總和進行關聯？

來源

2017-02-03 thecornman

我應該加入：我也嘗試過使用all_shortest_paths;返回所有具有最少邊數的路徑....我想我可以返回這組路徑並選擇具有最小加權邊的總和的路徑。但是，我無法弄清楚如何獲得這些路徑的加權邊的總和以伴隨它們。我得到最短路徑的生成器對象（根據邊的數量）....是否有一種簡單的方法來顯示加權邊和路徑的總和？ – thecornman

而不是使用浮點的權重，使用元組(weight, number_of_edges)成對添加。使用這些新權重的最低權重路徑將具有最低權重，並且在配合情況下是最短路徑。

要定義這些權重，我將使它們成爲tuple的子類，並重新定義__add__。那麼你應該可以使用你現有的代碼。

來源

2017-02-03 17:14:44 btilly

如何將權重設爲元組我有點困惑.......如果我將權重參數設置爲元組，networkx似乎不支持添加數據類型以獲取最短路徑距離 – thecornman

@thecornman使用在http://stackoverflow.com/a/15919466/585411解決方案來定義添加正確的元組。您將需要'從itertools import izip'，並且通過使用'mytup（（weight，length））'傳遞一個元組來構造權重。那些特殊的元組應該流經普通的python和Do The Right Thing。 – btilly

Python：最短加權路徑和最少邊數

回答

相關問題