问题描述:

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

(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|)`

.