我正在解决下面描述的问题，想不出比尝试每个组的每个顶点的每个置换更好的算法了。
我得到了一张顶点图，以及一组特定顶点的列表，目标是找到从特定起始顶点到特定结束顶点的最短路径，该路径必须通过每个指定顶点组中的至少一个顶点。图中也有不属于任何给定组的顶点。可以重新访问顶点和边。
图形数据指定如下：
- 顶点列表-每个顶点由一个序列号标识(0到顶点数-1)
- 边列表-顶点对列表(按顶点编号)
- 顶点组列表-矢量编号列表
- 一个特定的起点和终点
如果有任何更好的解决方案，我将不胜感激，谢谢。
摘要：
我们可以使用比特掩码来有效地检查到目前为止我们访问过哪些组，并将其与传统的BFS/Dijkstra的最短路径算法相结合。
如果我们假设必须包括的E边、V顶点和K顶点组，则下面的算法具有O((V + E) * 2^K)的时间复杂度和O(V * 2^K)的空间复杂度。指数2^K项意味着它只适用于相对较小的K，比如最多10或20。
详细信息：
首先，边缘是否加权？
如果是的话；"最短路径"；该算法通常是Dijkstra算法的变体，在该算法中，我们保留最短路径的(最小)优先级队列。我们只访问位于队列顶部的节点，这意味着这必须是到达该节点的最短路径。到该节点的任何其他较短路径都已经添加到优先级队列中，并且会在当前迭代之前出现。(注意：这不适用于负路径)。
如果没有，意味着所有边都具有相同的权重，则不需要维护具有最短边的优先级队列。相反，我们可以只运行常规的广度优先搜索(BFS)，在该搜索中，我们维护当前深度的所有节点的deque。在每一步中，我们迭代当前深度的所有节点(从deque的左侧弹出它们)，对于每个节点，我们将所有尚未访问的邻居添加到deque的右侧，形成下一个级别。
下面的算法适用于BFS和Dijkstra，但为了简单起见，对于其余的答案，我将假设边具有正权重，我们将使用Dijkstra's。然而，重要的是，对于任一算法；访问"；或"；探索"；路径的节点，该节点必须是到该节点的最短路径。这个性质对于算法的有效性至关重要，因为我们知道我们最多只访问一次V节点和E边中的每一个，这给了我们O(V + E)的时间复杂性。如果我们使用Dijkstra，我们必须将其与优先级队列使用的log(V)相乘(这也适用于摘要中提到的时间复杂性)。
我们的问题
在我们的例子中，我们有额外的复杂性，即我们有K顶点组，对于每个顶点组，我们的最短路径必须包含其中至少一个节点；最短电流路径"；。
例如，请参见此简单图表。符号：--表示边，start表示开始节点，end表示结束节点。值为0的顶点不具有顶点组，值为>= 1的顶点属于该索引的顶点组。
end -- 0 -- 2 -- start -- 1 -- 2
很明显，最优路径将首先向右移动到组1中的节点，然后向左移动直到结束。但对于我们上面介绍的BFS和Dijkstra算法来说，这是不可能的！在我们从开始向右移动以捕获组1中的节点之后，我们永远不会从左移回开始，因为我们已经用较短的路径到达了那里。
诀窍
在上面的例子中，如果右侧看起来像start -- 0 -- 0，其中0意味着顶点不属于一个组，那么去那里再回到起点是没有用的。
尽管道路会变得更长，但为什么去那里再回来是有意义的决定性原因是它包括了一个我们以前从未见过的群体。
我们如何跟踪在当前职位上是否包括一个团队？最有效的解决方案是位掩码。因此，例如，如果我们已经访问了组2和4的节点，那么比特掩码将在位置2和4处设置一个比特，并且它将具有2 ^ 2 + 2 ^ 4 == 4 + 16 == 20的值
在常规Dijkstra中，我们只保留一个大小为V的一维数组，以跟踪到每个顶点的最短路径是什么，初始化为非常高的MAX值。CCD_ 29以值CCD_。
我们可以修改此方法，使其具有维度为[2 ^ K][V]的二维数组，其中K是组的数量。每个值都初始化为MAX，只有array[mask_value_of_start][start]以0开头。
我们存储在array[mask][node]的值意味着给定位掩码值为mask的已访问组，到达该node的最短路径的长度是多少
突然，Dijkstra复活了
一旦我们有了这个结构，我们就可以突然再次使用Dijkstra的(BFS也是如此)。我们只是稍微改变一下规则：
- 在Dijkstra的常规中，我们从不重新访问节点
->在我们的修改中，我们通过CCD_ 39进行区分，并且如果某个节点已经针对该特定的CCD_。
- 在常规Dijkstra中，当探索一个节点时，我们会查看所有邻居，只有当我们设法减少到它们的最短路径时，才会将它们添加到优先级队列中
->在我们的修改中，我们查看所有邻居，并更新用于检查该邻居的掩码，如：neighbor_mask = mask | (1 << neighbor_group_id)。如果对于特定的array[neighbor_mask][neighbor]，我们设法减少了最小路径长度，那么我们只向优先级队列添加一个{neighbor_mask, neighbor}对。
- 在常规Dijkstra中，我们只访问具有当前最短路径的未探索节点，保证它是该节点的最短路径
->在我们的修改中，我们只访问尚未探索其相应mask值的节点。我们也只访问所有掩码中的当前最短路径，这意味着对于任何给定的mask，它必须是最短路径。
- 在常规Dijkstra中，一旦我们访问
end节点，我们就可以返回，因为我们确信我们得到了到达它的最短路径
->在我们的修改中，我们可以在访问完整mask的end节点时返回，这意味着掩码包含所有组，因为它必须是完整掩码的最短路径。这就是我们问题的答案。
如果速度太慢
就是这样！因为时间和空间复杂性指数依赖于组K的数量，所以这只适用于非常小的K(当然取决于节点和边的数量)。
如果这对你的需求来说太慢了，那么可能会有一个更复杂的算法，聪明的人可以想出，它可能涉及动态编程。
很可能这仍然太慢了，在这种情况下，你可能会想切换到一些启发式方法，为了获得更多的速度而牺牲准确性。