在最近的一次采访中，我被要求实现单源最短路径算法（用于无向和正加权图），并稍作修改，即我们获得了权重为“w”的额外边缘。我们必须找到一条比 SSSP 算法计算的路径更短的路径，通过在两个尚未连接的节点之间连接权重“w”的额外边。这是一张图片。根据 SSSP，A（源）和 D（目的地）之间的最短路径是 A-B-C-D，即总共 8 条。 https://i.stack.imgur.com/amkHH.jpg
但考虑到额外的优势。它可以连接在尚未连接的 A 和 D 之间，以最小化通过 SSSP 算法产生的最短路径。具有贡献最短路径的额外边的图的图像 https://i.stack.imgur.com/18rwE.jpg
我试着思考解决方案。但到目前为止还没有发生任何事情。我已经实现了 Dijkstra 算法来找到最短路径。但这个小小的修改却让我感到困惑。那么你能帮忙一点吗？
有两种选择：
我们不需要额外的优势。这种情况由标准 Dijkstra 算法处理。
具有额外边的最短路径如下所示：shortest_path(start, V) + (V, U) + shortest_path(U, target)。也就是说，我们从起点到某个顶点V通过原始图中的最短路径，然后我们去U（同样，任意顶点）通过添加这个额外的边（V and U一定不能连接）然后我们从U通过原图中的最短路径到达目标节点。
我们可以使用路径的结构来得到O(n ^ 2)解决方案：我们可以计算从起始节点到所有其他节点的最短路径（运行一次 Dijkstra 算法）以及从目标节点到所有其他节点的所有最短路径（再运行一次）。现在我们可以迭代所有可能的对(V, U)并选择最好的一个。
奖励：我们可以解决它O(m log n)对于稀疏图。想法如下：而不是检查所有(U, V)对，我们可以找到这样的U在所有未连接的顶点中，它与目标的距离最小V in degree(V) * log V（甚至线性）时间（这个问题称为查找不在集合中的最小元素）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
