找到遍历一组所需节点并 returns 到起点的最短路径
Find the shortest path that traverses through a required set of nodes and returns to the starting point
假设我有一组边的形式（其中每个元组 (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)]
和距离矩阵：
C=[2.5, 5.5, 1.0, 2.0, 1.0, 2.0, 1.0, 2.0, 1.0, 2.0, 2.5, 5.0, 2.0, 5.59, 5.0, 2.0, 5.0, 2.0, 5.0, 2.0]
其中 C 中的每个元素（比如第 i 个位置）对应于 E（第 i 个位置）中相应边的 2 个节点之间的距离。
现在，我想找到从原点（节点 1）开始，经过节点 2 和 4，然后 returns 到原点（一个循环）的最短路径。 Python 中的 NetworkX 包有办法做到这一点吗？或者是否有其他方法（计算成本不高）来做到这一点？
我查找了 https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html 与最短路径相关的函数，但我找不到适合我的问题的函数。对此有一些见解将不胜感激！
您可以将其分解为更简单的问题，我假设这些问题存在于 networkx 中。
让 E 和 V 分别成为原始图中的边数和顶点数。
让 F 成为循环中必须存在的顶点数（示例中为 3：节点 1、2 和 4）。从现在开始，我将它们称为循环顶点。
算法：
计算每个循环顶点之间的距离。如果使用 Dijkstra 算法，则每个循环顶点 O(E + V log V)，因此总共 O(FE + FV log V)。
使用步骤 1 中的边权重解决循环顶点上的旅行商问题，这将花费 O(F!)。如果这成为一个重要的瓶颈，则有一些时间复杂度更好的近似算法。
总费用为 O(max(FE, FVlogV, F!))。 F! 项很可能会占据主导地位。
假设我有一组边的形式（其中每个元组 (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)]
和距离矩阵：
C=[2.5, 5.5, 1.0, 2.0, 1.0, 2.0, 1.0, 2.0, 1.0, 2.0, 2.5, 5.0, 2.0, 5.59, 5.0, 2.0, 5.0, 2.0, 5.0, 2.0]
其中 C 中的每个元素（比如第 i 个位置）对应于 E（第 i 个位置）中相应边的 2 个节点之间的距离。
现在，我想找到从原点（节点 1）开始，经过节点 2 和 4，然后 returns 到原点（一个循环）的最短路径。 Python 中的 NetworkX 包有办法做到这一点吗？或者是否有其他方法（计算成本不高）来做到这一点？
我查找了 https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html 与最短路径相关的函数，但我找不到适合我的问题的函数。对此有一些见解将不胜感激！
您可以将其分解为更简单的问题，我假设这些问题存在于 networkx 中。
让 E 和 V 分别成为原始图中的边数和顶点数。
让 F 成为循环中必须存在的顶点数（示例中为 3：节点 1、2 和 4）。从现在开始，我将它们称为循环顶点。
算法：
计算每个循环顶点之间的距离。如果使用 Dijkstra 算法，则每个循环顶点
O(E + V log V)，因此总共O(FE + FV log V)。使用步骤 1 中的边权重解决循环顶点上的旅行商问题，这将花费
O(F!)。如果这成为一个重要的瓶颈，则有一些时间复杂度更好的近似算法。
总费用为 O(max(FE, FVlogV, F!))。 F! 项很可能会占据主导地位。