Finding shortest path distances in a graph containing at most two negative edges

 

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.

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?

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

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.

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.

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

  • First, a new node q is added to the graph, connected by zero-weight edges to each of the other nodes.
  • 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.
  • 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).
  • 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.

    • Just some definitions to start:

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

  • Define the start and end vertex of the shortest path we want to find as s and e respectively.

    • 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.

    The algorithm:

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

    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|) .

    链接地址: http://www.djcxy.com/p/35216.html

    上一篇: 对最短路径算法使用负权重？

    下一篇: 在包含至多两个负边的图中寻找最短路径距离