在最近的一次采访中，我被要求实现单源最短路径算法(用于无向和正加权图)并稍作修改，即我们获得了一个权重为“w”的额外边。我们必须找到是否可以找到比 SSSP 算法计算的路径更短的路径，方法是在尚未连接的两个节点之间连接权重为“w”的额外边。 Here's an image. As according to SSSP the shortest path between A(source) & D(destination)is A-B-C-D i.e. total of 8.
但考虑到额外的优势。它可以连接在尚未连接的 A 和 D 之间，以最小化通过 SSSP 算法产生的最短路径。 Image of graph with extra edge contributing the shortest path
我试着思考解决方案。但到目前为止没有任何进展。我已经实现了 Dijkstra 算法来找到最短路径。但是这个小小的修改让我感到困惑。那么你能帮点忙吗。
最佳答案
有两种选择:
我们不需要额外的优势。这种情况由标准 Dijkstra 算法处理。
具有额外边的最短路径如下所示:
shortest_path(start, V) + (V, U) + shortest_path(U, target)。也就是说，我们通过原始图中的最短路径从开始到某个顶点V，然后我们通过添加以下内容到达U(同样是任意顶点)额外的边(V和U不能连接)然后我们从U到目标节点通过原始路径中的最短路径图。我们可以使用路径结构来获得
O(n ^ 2)解决方案:我们可以计算从起始节点到所有其他节点的最短路径(一次运行Dijkstra 算法)和从目标节点到所有其他节点的所有最短路径(多运行一次)。现在我们可以遍历所有可能的对(V, U)并选择最好的对。奖励:对于稀疏图，我们可以在
O(m log n)中解决它。思路如下:不是检查所有(U, V)对，我们可以找到这样的U，它在所有顶点中到目标的距离最小在degree(V) * log V(甚至线性)时间内未连接到V(此问题被称为寻找不在集合中的最小元素)。
关于algorithm - 带有权重为 'w' 的额外边的 Dijkstra 单源最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40089933/