是否存在通过一组顶点 U 的最短路径
Does there exist a shortest path which goes through a group of vertices U
问题是在有向图中找到两个顶点之间的最短路径
将进入顶点 (u in U) 的边转换为两条边，并将进入非 u 顶点的边转换为 3 条边，有效地使通过 u 顶点的路径比非 u 顶点更短。如果存在一条等长的最短路径经过U中的所有u.
想法是然后运行 BFS 算法一次并检查最短路径是否包含 u 中的所有边并且与 s 和 t 之间的最短路径长度相等（将所有相乘的边带入帐户）。
编辑：抱歉，忘了问这个问题，这个算法正确吗？
你的算法思路可行。也就是说，您 运行 BFS 找到最短路径，然后 运行 BFS 再次在更改后的图形上进行，这样可以更好地通过 U。但是您描述的更改它的方式可能会改变最佳路径是。
问题来了。假设 P1 是一条通过所有 U 的更多步骤的最佳路径，而 P2 是一条从 U 到 U 经过昂贵的一跳的好路径，在更改之前 P1 可能比 P2 更好，但在更改权重之后，P2比P1好。于是你第二次找到P2，它没有遍历整个U，就误认为P1不存在。
要修复它，您必须为 entering/leaving U 设置固定奖励。所有边权重的变化相同。现在一条路径经过的 U 的节点越多越好，但是你没有改变两条路径的相对值，这两条路径经过相同数量的 U 的节点。现在你的推理没有陷阱。
OP 在这里，自发布问题以来我已经设法证明了算法。
证明：
如果存在最短路径 P1,P2,P3...Pn 然后通过将进入非 U 顶点的边乘以 3 和进入 U 顶点的边乘以 2 来扩充图形（我后来意识到扩充可以是2 和 1) 最短路径的长度为：
3 * |圆周率| - |{你 |你在 Pi}|
路径中的边数乘以3减去路径中U中的顶点数
很明显，最短路径是最小化 3 * |Pi| 的路径- |{你 |你在 Pi}|
但是 3*|Pi|是所有最短路径的常数，所以我们实际上想要最大化 |{u |你在 Pi}|
这意味着我们希望尽可能多地通过 u 中的顶点，因此如果通过使用 BFS 并恢复最短路径，我们发现它不包含 U 中的所有顶点，我们当然可以说这样路径不存在，如果我们确实发现有一条路径穿过 U 中的所有顶点，我们必须检查它的长度（在将其恢复为原始图中的路径之后）我们可以简单地检查它的长度是否为长度s 和 t 之间的最短路径如果是，那么它是一条穿过 U 中所有顶点的路径，并且是最短路径，如果不是，那么显然不是。
问题是在有向图中找到两个顶点之间的最短路径 将进入顶点 (u in U) 的边转换为两条边，并将进入非 u 顶点的边转换为 3 条边，有效地使通过 u 顶点的路径比非 u 顶点更短。如果存在一条等长的最短路径经过U中的所有u.
想法是然后运行 BFS 算法一次并检查最短路径是否包含 u 中的所有边并且与 s 和 t 之间的最短路径长度相等（将所有相乘的边带入帐户）。
编辑：抱歉，忘了问这个问题，这个算法正确吗？
你的算法思路可行。也就是说，您 运行 BFS 找到最短路径，然后 运行 BFS 再次在更改后的图形上进行，这样可以更好地通过 U。但是您描述的更改它的方式可能会改变最佳路径是。
问题来了。假设 P1 是一条通过所有 U 的更多步骤的最佳路径，而 P2 是一条从 U 到 U 经过昂贵的一跳的好路径，在更改之前 P1 可能比 P2 更好，但在更改权重之后，P2比P1好。于是你第二次找到P2，它没有遍历整个U，就误认为P1不存在。
要修复它，您必须为 entering/leaving U 设置固定奖励。所有边权重的变化相同。现在一条路径经过的 U 的节点越多越好，但是你没有改变两条路径的相对值，这两条路径经过相同数量的 U 的节点。现在你的推理没有陷阱。
OP 在这里，自发布问题以来我已经设法证明了算法。
证明：
如果存在最短路径 P1,P2,P3...Pn 然后通过将进入非 U 顶点的边乘以 3 和进入 U 顶点的边乘以 2 来扩充图形（我后来意识到扩充可以是2 和 1) 最短路径的长度为：
3 * |圆周率| - |{你 |你在 Pi}|
路径中的边数乘以3减去路径中U中的顶点数
很明显，最短路径是最小化 3 * |Pi| 的路径- |{你 |你在 Pi}|
但是 3*|Pi|是所有最短路径的常数，所以我们实际上想要最大化 |{u |你在 Pi}|
这意味着我们希望尽可能多地通过 u 中的顶点，因此如果通过使用 BFS 并恢复最短路径，我们发现它不包含 U 中的所有顶点，我们当然可以说这样路径不存在，如果我们确实发现有一条路径穿过 U 中的所有顶点，我们必须检查它的长度（在将其恢复为原始图中的路径之后）我们可以简单地检查它的长度是否为长度s 和 t 之间的最短路径如果是，那么它是一条穿过 U 中所有顶点的路径，并且是最短路径，如果不是，那么显然不是。