如何限制NetworkX图中的特定路径？

Question

我正在尝试使用Dijkstra和A Star算法计算两个点之间的最短路径，这个过程是在一个有向的NetworkX图中进行的。

目前这个功能运行得很好，我可以看到计算出的路径，但我想找到一种方法来限制某些路径。

比如说，如果我们有以下节点：

nodes = [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

你可以为节点1设置数据 {color=['blue']}，节点2的颜色设置为 {color=['red','blue']}，而节点3的颜色则是 {color=['red']}。然后可以使用 networkx.algorithms.astar_path() 方法，设置以下内容：

• 启发式函数（heuristic）要设置成一个，当遇到颜色不符合你要找的节点时，返回一个接近于无穷大的值。
• 权重（weight）要设置成小于无穷大的值。

Answer 2

这个问题很有趣，我之前没听说过，可能是因为我对这个话题了解不多，也没有太多使用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。

我希望这个回答至少能对你有所帮助，如果你找不到现有的解决方案。更复杂的限制规则会让图变得非常庞大，状态节点的数量会呈指数增长，所以这个算法要么太简单，要么这个问题很难解决；-）