Dijkstra算法——单源最短路径算法，带有一条额外边权值为'w'

Question

在最近的一次采访中，我被要求实现单源最短路径算法（用于无向正权图），稍作修改。我们会给你一条额外的边，其权重为'w'。我们需要找到一个更短的路径，连接两个未连接的节点，通过这条额外的边，优于SSSP算法计算出的路径。 这里是图片。根据SSSP，A（源）和D（目标）之间的最短路径是A-B-C-D，即总长为8。 但是，在给定了这条额外的边之后，可以将其连接在A和D之间（这两个点先前并没有连接），以缩小通过SSSP算法获得的最短路径。 含有额外边的图像，对最短路径的贡献 我尝试思考解决方案，但至今仍没有头绪。我已经实现了Dijkstra算法来寻找最短路径。但是这个小修改让我不知所措。所以，你可以帮我一下吗？

- Ravi Chandran

Answer 1

有两个选项：

1. 我们不需要额外的边。这种情况可以通过标准的 Dijkstra 算法处理。

2. 带有额外边的最短路径如下所示：`shortest_path(start, V) + (V, U) + shortest_path(U, target)`。也就是说，我们沿着原始图中的最短路径从起点到某个顶点 $V$，然后通过添加这条额外边（$V$ 和 $U$ 不得连接）前往 $U$（同样是任意顶点），最后再沿着原始图中的最短路径从 $U$ 到目标节点。

3. 我们可以利用路径结构来得到一个 $O(n^2)$ 的解法：我们可以计算从起始节点到所有其他节点的最短路径（一次 Dijkstra 算法运行）和从目标节点到所有其他节点的所有最短路径（再运行一次）。现在我们只需遍历所有可能的对 $(V, U)$ 并选择最佳的结果。

4. 奖励部分：我们可以针对稀疏图使用 $O(m\log n)$ 的解法。思路如下：我们不必检查所有 $(U,V)$ 对，而是可以在 $degree(V)\log V$（甚至是线性）时间内找到与目标距离最小的那个 $U$，该 $U$ 与 $V$ 不相连（这个问题被称为在集合中找到最小的元素）。

- kraskevich

Answer 2

我不确定我理解你的问题。你有一个带权图，可以添加权值为w的边，添加到哪里可以使最短路径。 我认为我们可以使用SPFA+DP来解决这个问题。将所有其他边设置为w，并创建布尔矩阵m，m[i,j]=1表示i和j之间没有边，dp[u,0]表示在不使用额外边的情况下到达u的最短距离，dp[u,1]表示使用一条额外边的情况。我没写dp转移方程。所以我们可以在SPFA中迭代，并且回溯最佳的dp方式并获得设置额外边的位置。 我们在上述解决方案中没有使用Dijkstra算法。

SPFA也是单源最短路算法，它可以处理负权重边，但不能处理负环。

这只是我的想法，我还没有尝试过，但我认为这是一个解决问题的思路。如果有任何错误，请告诉我。

- AnRiyomta