Dijkstra的单一来源Shourtest路径的重量为'w' [英] Dijkstra's Single Source Shourtest Path with an extra edge with weight of 'w'

问题描述

在最近的一次采访中，我被要求实施单源最短路径算法（对于无向和正向加权图），稍作修改，即我们得到一个重量为w的额外边缘。我们必须通过在两个尚未连接的节点之间连接额外的边以及权重w来找到是否可以找到比SSSP算法计算的更短的路径。
这是一张图片。根据SSSP，A（来源）& D（目的地）是A-B-C-D，即总数为8.

但有额外的优势。它可以连接在尚未连接的A和D之间，以最小化通过SSSP算法产生的最短路径。
带有额外边缘的图形图像有助于缩短最短路径

我试着想过解决方案。但迄今为止还没有发生。我已经实现了Dijkstra算法来寻找最短路径。但是这个小小的修改让我感到困惑。所以你可以帮助一下。

解决方案

有两种选择：

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

2. 具有额外边的最短路径如下所示： shortest_path（start，V ）+（V，U）+最短路径（U，目标）。也就是说，我们从最初的图中最短路径开始到顶点 V ，然后我们转到 U V 和 U 不得连接）而不是我们通过原始图中的最短路径从 U 到目标节点。




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

>奖金：我们可以在 O（m log n）中为一个稀疏图解解。这个想法如下：不是检查所有（U，V）对，我们可以找到这样的 U 它在度（V）* log V 中没有连接到 V 的所有顶点中， （甚至线性）时间（这个问题被称为找到不在集合中的最小元素）。

In an recent interview I was asked to implement single source shortest path algorithm(for undirected and positive weighted graph) with slight modification i.e. we're given an extra edge with weight 'w'. And we have to find if we can find a more shorter path, than the one calculated by SSSP algo, by connecting that extra edge, with weight 'w', between two nodes which are not already connected. 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.

But given the extra edge. It can be connected between A and D, which are not already connected, to minimize the shortest path yielded through SSSP algo. Image of graph with extra edge contributing the shortest path

I tried thinking about the solution. But nothing struck so far. I've implemented the Dijkstra algorithm to find the shortest path. But this little modification has baffled me. So can you help a little bit.

解决方案

There are two options:

1. We don't need an extra edge. This case is handled by a standard Dijkstra algorithm.

2. A shortest path with an extra edge looks like this: shortest_path(start, V) + (V, U) + shortest_path(U, target). That is, we go from the start to some vertex V by the shortest path in the original graph, then we go to U (again, an arbitrary vertex) by adding this extra edge (V and U mustn't be connected) and than we go from U to the target node by the shortest path in the original graph.

3. We can use the structure of the path to get an O(n ^ 2) solution: we can compute shortest paths from the start node to all the others (one run of the Dijkstra's algorithm) and all shortest paths from the target node to all other nodes (one more run). Now we can just iterate over all possible pairs (V, U) and pick the best one.

4. Bonus: we can solve it in O(m log n) for a sparse graph. The idea is as follows: instead of checking all (U, V) pairs, we can find such U that it has the minimal distance to the target among all vertices that are not connected to V in degree(V) * log V (or even linear) time (this problem is known as finding the smallest element not in the set).

这篇关于Dijkstra的单一来源Shourtest路径的重量为'w'的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！