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):
Just some definitions to start:
Let the negative edges be
n1 = (n1s, n1e) (i.e. from vertex
n1s to vertex
n2 = (n2s, n2e).
Define the start and end vertex of the shortest path we want to find as
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.
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|).