networkx中的约束短路径算法？

html5 • 2022年9月17日 pm7:45 • 问答

我正在使用 networkx 来解决最短路径问题。我主要使用shortest_path。我想知道，使用当前版本的 networkx，是否可以限制最短路径计算？

下面的示例生成了 A 和 G 之间的这两条最短路径：

左边的图片显示了最小化“长度”属性时的最佳路线，右边的图片显示了最小化“高度”属性时的最佳路线。

如果我们计算这些路线的统计数据，我们会得到：

Best route by length: ['A', 'B', 'E', 'F', 'D', 'G']
Best route by height: ['A', 'C', 'E', 'G']
Stats best routes: {
                   'by_length': {'length': 13.7, 'height': 373.0}, 
                   'by_height': {'length': 24.8, 'height': 115.0}
                   }

Best route by length: ['A', 'B', 'E', 'F', 'D', 'G']
Best route by height: ['A', 'C', 'E', 'G']
Stats best routes: {
                   'by_length': {'length': 13.7, 'height': 373.0}, 
                   'by_height': {'length': 24.8, 'height': 115.0}
                   }

有没有办法在计算最短路径时添加约束？（例如，通过最小化长度属性来计算最短路径，但同时保持height<300

计算图网络的代码：

编辑 07/06/21

我的问题可能太大而无法使用蛮力解决方案。

我还在networkx 讨论页中打开了一个帖子，似乎可以实现一个特殊的类，它在single_source_dijkstra. 然而，这个解决方案并不完美：如果有两条可接受的短路径（在高度上），算法将找到较短的一条，而不管其高度如何。当存在可接受的路径时，这会使看起来不可能到达目标节点......（更多详细信息：https : //github.com/networkx/networkx/discussions/4832#discussioncomment-778358）

以上是networkx中的约束短路径算法？的全部内容。

THE END

二维码