查找起始目的地與路徑長度約束之間的所有路徑

Question

我正在使用python 2.7和networkx。

我有一個相當大的網絡，我需要找到原點和目的地之間的所有路徑（不僅是最短路徑）。由於我的網絡很大，我想加快一些約束條件，例如路徑長度，成本等。

我正在使用networkx。我不想使用all_simple_paths，因爲對於all_simple_paths，我必須稍後根據路徑長度（節點數量）或路徑成本（基於弧成本）過濾所有路徑。過濾所有路徑對於大型網絡而言非常昂貴。

我真的很感激任何幫助。

Answer 1

這實際上取決於你在找什麼路徑。

首先，最短路徑爲您提供長度約束上的最小邊界c_min。然後給定長度限制c>=c_min，對於每個節點n，您知道最短路徑P_s_n和距離c_n從開始到此節點。選擇那些滿足c_n <c的節點。然後，您可以任意地從n到目標任意路徑延伸P_s_n，這將滿足您的長度限制。