networkx中的约束短路径算法？

Question

我正在使用 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}
                   }

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

计算图网络的代码：

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}
                   }

编辑 07/06/21

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

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

Answer 1

近似解决方案：

• 按长度运行最短
• 如果高度在限制范围内，则完成
• 删除路径中高度最大的链接
• 重复直到完成。

障碍：

• 如果具有最大高度的路径链接至关重要，则删除它将使目的地无法到达。如果发生这种情况，则有必要返回，替换最高的链接并删除第二高的链接......

• 不能保证找到最佳路径。