java - 节点加权图中的最大 N 节点连通子图

Question

以这个节点加权图为例：

• 恰好包含 1 个节点（和“入口点”）的最大子图将是 14。
• 恰好包含 2 个节点（和“入口点”）的最大子图将是 14 / 9。
• 恰好包含 3 个节点（和“入口点”）的最大子图将是 3 / 19 / 15。
• 恰好包含 4 个节点（和“入口点”）的最大子图将是 14 / 1 / 7 / 240。

我想不出比蛮力更好的方法来获得最大子图。
如果没有已知的有效算法，在这种情况下是否会找到遗传算法（交叉似乎很棘手）？

Answer 1

我认为你可以修改Dijkstra 的算法来解决这个问题。

使用 Dijkrasta 的算法，您正在求解最短路径。只需更改它即可找到最大路径。要将其限制在图中仅 1、2、3 个节点，请跟踪“访问”时到达每个节点所需的节点数。当没有其他节点的数量少于您要查找的节点数时停止。