如何限制NetworkX图中的某些路径？

Question

我试图使用Dijkstra和A Star算法(在有向NetworkX图中)计算2点之间的最短路径.

目前它工作正常,我可以看到计算的路径,但我想找到一种限制某些路径的方法.

例如,如果我们有以下节点:

节点= [1,2,3,4]

有这些边缘:

edges =((1,2),(2,3),(3,4))

有没有办法阻止/限制 1 - > 2 - > 3但仍允许2 - > 3&1 - > 2.

这意味着:

• 可以从1到2旅行

• 可以从2到3旅行

• 不能直接或间接地从1到3行进(即限制1-> 2-> 3路径).

这可以在NetworkX中实现..如果没有在Python中有另一个图形库允许这个吗？

谢谢.

Answer 1

有趣的问题，我从来没有听说过这个问题，可能是因为我在这个主题上没有太多的背景，也没有太多的 NetworkX 经验。不过，我确实有一个算法的想法。这可能只是最简单的方法，我很高兴听到更聪明的算法。

这个想法是，您可以使用限制规则将图转换为所有边都有效的新图，使用以下算法。

路径 (1,2,3) 的限制可以分为两个规则：

• 如果你过来了 (1,2) 那么移除 (2,3)
• 如果留下 (2,3)，则删除 (1,2)

要将其放入图表中，您可以为每种情况插入节点 2 的副本。在相应情况下，我将在有效边之后调用新节点1_2和2_3 。对于这两个节点，您复制所有传入和传出边缘减去受限边缘。

例如：

Nodes = [1,2,3,4]
Edges = [(1,2),(2,3),(4,2)]

有效路径只能是 4->2->3，而不是 1->2->3。所以我们把图展开：

Nodes = [1,1_2,2_3,3,4] # insert the two states of 2
Edges = [ # first case: no (1_2,3) because of the restriction 
          (1,1_2), (4, 1_2)
          # 2nd case, no (1,2_3)
          (2_3,3), (4,2_3)]

该图中唯一有效的路径是 4->2_3->3。这简单地映射到原始图中的 4->2->3。

如果您找不到现有的解决方案，我希望这个答案至少可以帮助您。较长的限制规则会导致图的状态节点数量呈指数增长，因此要么这个算法太简单，要么问题很难;-)