问题：给定无向图G，顶点集V的子集H（即H是V的子集）和起始顶点s（s在V中）。
设计一种算法，该算法查找从s到所有顶点的最短路径的长度，以使路径不经过H中的任何中间顶点（这意味着您可以终止于H中的一个顶点，但不能经过H中的某个顶点顶点（以H为单位）。（如果没有这样的路径，则将长度设置为∞。所有边的长度都相同。）
（算法的输出应为类似于BFS和Dijkstra的dist数组的数组。）
jiaoshi_910 回答：给定无向图设计算法
有一个简单的方法可以解决此问题：
- 为
V - H运行Dijkstra，即除H中的节点以外的所有节点。令输出为dist。 - 对于
i中的每个节点H，最短路径的长度为min {dist[j] + w[i][j]}，其中min应用于{{1 }}（如果我们有一个邻接列表而不是矩阵，可以提高效率。）
因此，基本上，使用Dijkstra在j中找到到节点 not 的最短路径。这样，到V-H中节点的最短路径就是从H中的节点到自身的最短扩展。 （对于H中未直接连接到V-H的节点，它们将∞作为问题状态。）
根据@jrook的评论，您提到所有边缘的长度都相同。然后，可以使用BFS代替Dijkstra。
另一个解决方案是在图形的修改版本上运行BFS：
- 同时删除
H中节点内的所有边缘。 - 使
V-H和H中的节点之间的边缘指向从V-H到H的方向。 - 通过在两个方向上添加有向边来使所有其他边（即
V-H中的节点之间的边）有向。
在此修改后的有向图中，您可以应用BFS或Dijkstra来找到所需条件的最短路径。