查找起始目的地与路径长度约束之间的所有路径

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，这将满足您的长度限制。