找到穿过所需节点集并返回起始点的最短路径

Question

假设我有一组边的形式（其中每个元组（I，j）是从节点I到节点j的有向边）：

E=[(1, 6), (1, 7), (2, 3), (2, 6), (3, 2), (3, 8), (4, 5), (4, 7), (5, 4), (5, 9), (6, 1), (6, 7), (6, 2), (7, 1), (7, 6), (7, 4), (8, 9), (8, 3), (9, 8), (9, 5)]

以及距离矩阵：

^{pr2}$

其中C（例如在第i个位置）中的每个元素对应于E（在第i个位置）中对应边的2个节点之间的距离。在

现在，我想找出从原点（节点1）开始的最短路径，它经过节点2和节点4，然后返回原点（一个循环）。对于Python中的NetworkX包，有没有办法做到这一点？或者是否有其他方法（计算成本不高）？在

{我找不到最短路径，但是我找不到最短路径。。对此我们深表感激！在

Answer 1

您可以将其分解为更简单的问题，我假设networkx中存在这些问题。在

让E和{}分别是原始图中的边数和顶点数。 让F是循环中必须包含的顶点数（在您的示例中为3：节点1、2和4）。从现在起，我将它们称为循环顶点。在

算法：

1. 计算每个周期顶点之间的距离。如果使用Dijkstra算法，每个循环顶点的O(E + V log V)，因此总共O(FE + FV log V)。

2. 使用步骤1中的边权重来解决循环顶点上的旅行商问题，这将花费O(F!)。如果这成为一个重要的瓶颈，有一些近似算法具有更好的时间复杂度。

总成本为O(max(FE, FVlogV, F!))。很可能F!项将占主导地位。在