Summary:
我们可以使用位掩码来有效地检查到目前为止我们访问过哪些组，并将其与传统的 BFS/Dijkstra 的最短路径算法相结合。
如果我们假设E edges, V顶点，和K必须包含的顶点组，以下算法的时间复杂度为O((V + E) * 2^K)以及空间复杂度为O(V * 2^K)。指数2^K术语意味着它只适用于相对较小的K，比如说最多 10 或 20。
Details:
首先，边缘是否加权？
如果是，那么“最短路径”算法通常是以下算法的变体迪杰斯特拉算法，其中我们保留最短路径的（最小）优先级队列。我们只访问位于队列顶部的节点，这意味着这必须是到达该节点的最短路径。到该节点的任何其他较短路径都已被添加到优先级队列中，并且将出现在当前迭代之前。 （注意：这不适用于负路径）。
如果不是，意味着所有边具有相同的权重，则无需维护具有最短边的优先级队列。我们可以只运行常规的广度优先搜索（BFS），其中我们维护一个包含当前深度的所有节点的双端队列。在每一步中，我们都会迭代当前深度的所有节点（从双端队列的左侧弹出它们），对于每个节点，我们将所有尚未访问的邻居添加到双端队列的右侧，形成下一个级别。
下面的算法适用于 BFS 和 Dijkstra 算法，但为了简单起见，对于答案的其余部分，我将假设边缘具有正权重，并且我们将使用 Dijkstra 算法。但重要的是，对于任何一种算法，我们都只会“访问”或“探索”一个节点，以获得一条必须是到该节点的最短路径的路径。这个属性对于算法的高效至关重要，因为我们知道我们最多会访问每个V节点和E仅边缘一次，给我们一个时间复杂度 of O(V + E)。如果我们使用 Dijkstra，我们必须将其乘以log(V)对于优先级队列的使用（这也适用于摘要中提到的时间复杂度）。
我们的问题
在我们的例子中，我们有额外的复杂性K顶点组，对于每个顶点组，我们的最短路径必须包含至少一个其中的节点。这是一个大问题，因为它破坏了我们简单地遵循“最短当前路径”的能力。
例如，参见这个简单的图表。符号：--表示边缘，start是起始节点，并且end是结束节点。有值的顶点0没有顶点组和具有值的顶点>= 1属于该索引的顶点组。
end -- 0 -- 2 -- start -- 1 -- 2
显然，最优路径首先会向右移动到组内节点1，然后向左移动直至结束。但这对于我们上面介绍的BFS和Dijkstra算法来说是不可能做到的！当我们从开始向右移动以捕获组中的节点后1，我们永远不会向左回到起点，因为我们已经用更短的路径到达了那里。
伎俩
在上面的例子中，如果右侧看起来像start -- 0 -- 0, where 0意味着该顶点不属于一个组，那么去那里并返回起点是没有用的。
尽管路会变得更长，但去那里再回来是有意义的，决定性的原因是其中包括一群我们以前从未见过的人.
我们如何跟踪当前位置是否包含某个组？最有效的解决方案是bit mask。因此，如果我们已经访问了组的一个节点2 and 4，那么位掩码将在该位置设置一个位2 and 4，它的值为2 ^ 2 + 2 ^ 4 == 4 + 16 == 20
在常规 Dijkstra 中，我们只保留一个大小为的一维数组V跟踪到每个顶点的最短路径是什么，初始化为非常高MAX value. array[start]从价值开始0.
我们可以修改此方法以改为具有二维数组[2 ^ K][V], where K是组数。每个值都被初始化为MAX, only array[mask_value_of_start][start]开始于0.
我们存储的值array[mask][node] means 给定已访问过的组，其位掩码值为mask，到达此点的最短路径的长度是多少node?
突然，Dijkstra复活了
一旦我们有了这个结构，我们就可以突然再次使用 Dijkstra 的结构（对于 BFS 来说是一样的）。我们简单地改变一下规则：
- 在常规 Dijkstra 中，我们永远不会重新访问节点
--> 在我们的修改中，我们通过以下方式区分mask如果某个节点已经被访问过，则永远不会重新访问该特定节点mask.
- 在常规 Dijkstra 中，当探索一个节点时，我们会查看所有邻居，并且只有在我们设法减少到它们的最短路径时才将它们添加到优先级队列中。
--> 在我们的修改中，我们查看所有邻居，并更新我们用来检查该邻居的掩码，例如：neighbor_mask = mask | (1 << neighbor_group_id)。我们只添加一个{neighbor_mask, neighbor}与优先级队列配对，如果对于特定的array[neighbor_mask][neighbor]我们设法减少了最小路径长度。
- 在常规 Dijkstra 中，我们只访问具有当前最短路径的未探索节点，保证它是到该节点的最短路径
--> 在我们的修改中，我们只访问各自的节点mask价值尚未探索。我们也只访问所有掩码中当前最短的路径，这意味着对于任何给定的mask它一定是最短路径。
- 在常规 Dijkstra's 中，我们可以在参观完后返回
end节点，因为我们确信我们得到了到达它的最短路径。
--> 在我们的修改中，我们可以在访问后返回end完整的节点mask，表示包含所有组的掩码，因为它必须是完整掩码的最短路径。这就是我们问题的答案。
如果这太慢了...
就是这样！因为时间和空间复杂度与组的数量呈指数关系K，这只适用于非常小的K（当然取决于节点和边的数量）。
如果这对于您的要求来说太慢，那么可能有一个更复杂的算法，更聪明的人可以想出，它可能会涉及动态规划.
这很可能仍然太慢，在这种情况下，您可能需要切换到某些启发式，牺牲准确性以获得更快的速度。
