具有最大数量特殊节点的特殊节点的图形中的简单路径
simple path in Graph with special nodes with max amount of special nodes
我有这个问题：
给定一个图 G = (V,E)，它有一个名为 R 的节点子集，它们是“特殊”节点。特殊节点的数量视情况而定。该图可以是有向的，无向的，没有权重，并且可以包含循环。
现在，我需要一种算法来找到从节点 s 到节点 t 的路径，该路径经过 R 中最大数量的“特殊”节点。
我知道这个问题是 np-hard 问题，很容易从哈密尔顿路径简化，但我一直在寻找不同的方法来解决它，而不必强制所有路径。
第一次尝试
首先，我尝试对图形进行一些预处理，其中每条通往“正常”节点的边的权重为 2，而通往 R 中节点的每条边的权重为 0。
然后我会在图表上 运行 dijkstra。
反例可能如下所示：
在此图中，dijkstra 会选择路径 [s,4,t]，即使路径 [s,1,2,3,t] 是具有最大数量红色节点的实际简单路径
第二次尝试
我的第二次尝试有点复杂。在这次尝试中，我将 运行 来自 s 节点和图中每个 R 节点的 bfs。然后我会创建一个新的可达性图，它可以模拟哪些 R 节点相互连接。
这种方法将 运行 解决任何有环或无向图中的主要问题，因为原始图中不存在的 R 节点之间的连接将包含在新图中。
因此，如果有人对我可以采取的任何智能预处理步骤出价，我将非常高兴
你的第一个方法好像不错，例如：
- R = 1 中某个节点 v 的所有边的权重
- 其余边的权重 = 0
然后 运行 Dijkstra 的截止值 = 最大特殊节点
我有这个问题： 给定一个图 G = (V,E)，它有一个名为 R 的节点子集，它们是“特殊”节点。特殊节点的数量视情况而定。该图可以是有向的，无向的，没有权重，并且可以包含循环。
现在，我需要一种算法来找到从节点 s 到节点 t 的路径，该路径经过 R 中最大数量的“特殊”节点。
我知道这个问题是 np-hard 问题，很容易从哈密尔顿路径简化，但我一直在寻找不同的方法来解决它，而不必强制所有路径。
第一次尝试
首先，我尝试对图形进行一些预处理，其中每条通往“正常”节点的边的权重为 2，而通往 R 中节点的每条边的权重为 0。 然后我会在图表上 运行 dijkstra。
反例可能如下所示：
在此图中，dijkstra 会选择路径 [s,4,t]，即使路径 [s,1,2,3,t] 是具有最大数量红色节点的实际简单路径
第二次尝试
我的第二次尝试有点复杂。在这次尝试中，我将 运行 来自 s 节点和图中每个 R 节点的 bfs。然后我会创建一个新的可达性图，它可以模拟哪些 R 节点相互连接。
这种方法将 运行 解决任何有环或无向图中的主要问题，因为原始图中不存在的 R 节点之间的连接将包含在新图中。
因此，如果有人对我可以采取的任何智能预处理步骤出价，我将非常高兴
你的第一个方法好像不错，例如：
- R = 1 中某个节点 v 的所有边的权重
- 其余边的权重 = 0
然后 运行 Dijkstra 的截止值 = 最大特殊节点