在包含最多两个负边的图中找到最短路径的距离。

I am given a directed graph where each edge has a cost.Taking advantage of the fact that there are at most two negative edges in the graph, my goal is to find shortest path distances from a given node s to all the nodes in V. The time complexity of the algorithm should be O(|E| + |V|*log|V|), so I think I need to apply Dijkstra's algorithm.

我有一个有向图，每条边都有代价。利用这一事实,最多有两个负边的图,我的目标是找到最短路径距离给定节点到所有节点在诉算法的时间复杂度是O(E | | + | V *日志| | |),所以我觉得我需要使用迪杰斯特拉算法。

I am guessing that I need to translate my given graph somehow to a new graph with non-negative weights that a shortest path from s to v in this graph will be equivalent to the required shortest path in the given graph.. or maybe I need to modify Dijkstra's algorithm?

我猜我需要把我的给定图转换成一个新的非负权图，这个图中从s到v的最短路径将等于给定图中所要求的最短路径。或者我需要修改Dijkstra的算法?

I am struggling right now. Any help would be appreciated!

我现在正在挣扎。如有任何帮助，我们将不胜感激!

2 个解决方案

#1

Since Dijkstra's algorithm is greedy, it won't work with negative weights. You need some other algorithm like the Bellman-Ford Algorithm for this purpose.

因为Dijkstra算法是贪心的，所以它不能处理负权值。你需要一些其他的算法，比如Bellman-Ford算法。

But, if you still want to use Dijkstra's algorithm, there is a known way. In this method, you need to reassign costs, so that all become positive.

但是，如果你仍然想使用Dijkstra算法，有一个已知的方法。在这种方法中，您需要重新分配成本，以便所有成本都变成正数。

For that you can check out Johnson's Algorithm. Johnson's algorithm consists of the following steps (taken from Wikipedia):

你可以看看约翰逊的算法。Johnson的算法包括以下步骤(取自Wikipedia):

First, a new node q is added to the graph, connected by zero-weight edges to each of the other nodes.
首先，向图中添加一个新的节点q，通过零权边连接到其他每个节点。
Second, the Bellman–Ford algorithm is used, starting from the new vertex q, to find for each vertex v the minimum weight h(v) of a path from q to v. If this step detects a negative cycle, the algorithm is terminated.
其次，使用Bellman-Ford算法，从新的顶点q开始，为每个顶点v查找从q到v的路径的最小权值h(v)。
Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm: an edge from u to v, having length w(u,v), is given the new length w(u,v) + h(u) − h(v).
下一个原始图像的边缘使用计算的值再加权bellman算法:从u,v,长度w(u,v),给出新的长度w(u,v)+ h(u)−h(v)。
Finally, q is removed, and Dijkstra's algorithm is used to find the shortest paths from each node s to every other vertex in the reweighted graph.
最后，去掉q，使用Dijkstra算法在重新加权的图中找到每个节点s到每个其他顶点的最短路径。

#2

Just some definitions to start:

只是一些定义:

Let the negative edges be n1 = (n1s, n1e) (i.e. from vertex n1s to vertex n1e)
and n2 = (n2s, n2e).

设负边为n1 = (n1s, n1e)(即从顶点n1s到顶点n1e)， n2 = (n2s, n2e)。
Define the start and end vertex of the shortest path we want to find as s and e respectively.

定义最短路径的起点和终点分别为s和e。

The basic idea:

它的基本思想是:

Run Dijkstra's algorithm multiple times for each combination of the starting vertex and each end vertex of the negative-weight edges as the starting point and the end vertex and each start vertex of the negative-weight edges as the ending point, and use these values to find the actual shortest path.

对负权边的每一个起始点和每一个结束点作为起始点，对负权边的每一个起始点和每一个起始点作为结束点运行Dijkstra算法多次，并利用这些值找到实际的最短路径。

The algorithm:

该算法:

Use Dijkstra's algorithm to determine the following shortest paths, all excluding both negative edges:

使用Dijkstra算法确定以下最短路径，所有路径都不包括两条负边:

se   = s -> e                  // shortest path from s to e
sn1  = s -> n1s                // shortest path from s to n1
sn2  = s -> n2s                // shortest path from s to n2
ne1  = n1e -> e                // shortest path from n1 to e
n1n2 = n1e -> n2s              // shortest path from n1 to n2
ne2  = n2e -> e                // shortest path from n2 to e
n2n1 = n2e -> n1s              // shortest path from n2 to n1

Now simply calculate the minimum of:

现在只需计算最小值:

se                             // s to e
sn1 + n1 + ne1                 // s to n1 to e
sn2 + n2 + ne2                 // s to n2 to e
sn1 + n1 + n1n2 + n2 + ne2     // s to n1 to n2 to e
sn2 + n2 + n2n1 + n1 + ne1     // s to n2 to n1 to e

Since there's a constant 7 runs of Dijkstra's algorithm,
the running time will be O(7(|E| + |V| log |V|)) = O(|E| + |V| log |V|).

由于Dijkstra算法有7次恒定运行，运行时间为O(7(|E| + |V| log |V|)) = O(|E| + |V| log |0 V |1)。

#1