11

我正在尝试使用 Dijkstra 和 A Star 算法（在有向 NetworkX 图中）计算 2 点之间的最短路径。

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

例如，如果我们有以下节点：

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

使用这些边缘：

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

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

这意味着：

  • 可以从 1 到 2

  • 可以从 2 到 3

  • 不能直接或间接地从 1 移动到 3 ..（即限制 1->2->3 路径）。

这可以在 NetworkX 中实现吗？如果没有，Python 中是否有另一个图形库允许这样做？

谢谢。

4

2 回答 2

4

有趣的问题，我从来没有听说过这个问题，可能是因为我对这个主题没有太多的背景，对 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。

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

于 2011-11-02T17:41:03.143 回答
3

您可以为节点 1 设置节点数据 {color=['blue']}，节点 2 有 {color=['red','blue']}，node3 有 {color=['red']}。然后使用networkx.algorithms。astar_path() 方法设置

  • 启发式设置为一个函数，当它遇到一个与您正在搜索的颜色不同的节点时，它会返回一个 might_as_well_be_infinity
  • 重量=小于无穷大。
于 2015-11-13T02:28:08.340 回答