列出所有可能的“最短”路径

Question

我遇到了一个组合问题，这个问题可以看作是一个网络搜索问题。为了更好地可视化并使用已经实现的功能，我决定使用networkx这个库（其实我没有足够的时间去用其他方式实现）。

我的问题比较复杂，但我会尽量从最简单的地方开始讲解，以便大家理解。总的来说，我需要找出到达树的终点节点的组合。

下面的图是一个简单的例子：

enter image description here

在这个例子中，B、D、F、H是终点节点，而起点用O表示。所以，一个路径组合可能是：

OAB
OCD
OED
OEF
OH
OGH

不过，我实际上是想寻找到达终点节点的“最短”或“最优”路径。这个图（或者说边）并没有提供关于路径“成本”的任何信息。成本的评估将根据找到的组合结果来进行。评估这些组合的“实际”成本是计算上非常耗费资源的。虽然这个图提供的信息不多，但有一点是明确的：为了到达H，OH始终比OGH更好。因此，组合OGH可以从可能的组合列表中排除。这本质上就像是距离的度量。

还有一点，实际上D和F是等效的节点（它们是不同的节点，但在我的应用中意义相同）。这样的信息只有在两个节点

- see each other
- see exactly the same nodes

仔细观察图形，我们还可以发现C和E也是等效节点。所以，更具体地说：组合OCD和OED实际上是相同的。一旦OCD被添加到组合列表中，就不需要再添加OED。从图中也可以看出，由于D和F是相同的，一旦OCD被添加到列表中，就不需要再添加OCF。

总之，在这种情况下，解决方案是：

OAB
anyone of OCD, OED, OCF, OEF
OH

为了绘制这个图，我参考了networkx的教程，然后创建了下面的代码：

import networkx as nx
import matplotlib.pyplot as plt

graph = [('O', 'A'), ('O', 'C'),  ('O', 'E'),  ('O', 'G'),  ('O', 'H'),  
         ('A', 'B'), ('A', 'O'),
         ('B', 'A'),
         ('C', 'D'), ('C', 'E'), ('C', 'F'), ('C', 'O'),
         ('D', 'E'), ('D', 'C'), ('D', 'F'),  
         ('E', 'C'), ('E', 'D'), ('E', 'F'), ('E', 'O'),
         ('F', 'C'), ('F', 'D'), ('F', 'E'),
         ('G', 'H'), ('G', 'O'), 
         ('H', 'G'), ('H', 'O')]

G=nx.DiGraph()
for edge in graph:
    G.add_edge(edge[0], edge[1])

pos=nx.graphviz_layout(G,prog='dot')
nx.draw(G, pos)
plt.show()

所以，我的问题是希望能列出这样的序列，使用任何工具箱，但最好是networkx。第一步可能是简化（或减少）图形，然后再创建一个图对象。一旦得到了简化的图形，就可以使用nx.all_simple_path命令列出所有的替代路径。我需要你的帮助来进行这样的图形简化。

我的图形不深，通常和例子中的大小差不多。

组合问题最短路径图论 networkx 成本评估网络搜索图形简化等效节点

列出所有可能的“最短”路径

1 个回答

撰写回答