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

Question

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!

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

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

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

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

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