Dijkstra 的单源最短路径，带有权重为 'w' 的额外边

Question

在最近的一次采访中，我被要求通过稍微修改实现单源最短路径算法（用于无向和正加权图），即我们获得了一个权重为“w”的额外边。我们必须找到一条比 SSSP 算法计算出的路径更短的路径，通过在两个尚未连接的节点之间连接权重为“w”的额外边。 这是一张图片。根据SSSP，A（源）和D（目的地）之间的最短路径是ABCD，即总共8条。

但考虑到额外的优势。它可以连接在尚未连接的 A 和 D 之间，以最小化通过 SSSP 算法产生的最短路径。 具有贡献最短路径的额外边的图的图像

我试着思考解决方案。但到目前为止还没有发生任何事情。我已经实现了 Dijkstra 算法来找到最短路径。但是这个小小的修改让我很困惑。所以你能不能帮点忙。

Answer 1

有两种选择：

1. 我们不需要额外的优势。这种情况由标准的 Dijkstra 算法处理。

2. 一个额外的边缘的最短路径是这样的：shortest_path(start, V) + (V, U) + shortest_path(U, target)。也就是说，我们V通过原始图中的最短路径从起点到某个顶点，然后U通过添加这条额外的边（V并且U不能连接）来到达（再次，任意顶点），然后我们从U到原图中最短路径的目标节点。

3. 我们可以使用路径的结构来获得O(n ^ 2)解决方案：我们可以计算从起始节点到所有其他节点的最短路径（Dijkstra 算法的一次运行）以及从目标节点到所有其他节点的所有最短路径（再运行一次） ）。现在我们可以迭代所有可能的对(V, U)并选择最好的一对。

4. 奖励：我们可以O(m log n)用稀疏图来解决它。这个想法是如下：而不是检查所有(U, V)对，我们可以找到这样的U，它有没有连接到所有顶点中到目标的最小距离V的degree(V) * log V（甚至是线性）时间（这个问题被称为寻找最小的元素不在集合中）。