Shortest path distance from source(s) to all nodes in the graph - O(m + n log(n)) time

Question

Let G(V,E) be a directed weighted graph with edge lengths, where all of the edge lengths are positive except two of the edges have negative lengths. Given a fixed vertex s, give an algorithm computing shortest paths from s to any other vertex in O(e + v log(v)) time.

My work:

I am thinking about using the reweighting technique of Johnson's algorithm. And then, run Belford Algo once and apply Dijkstra v times. This will give me the time complexity as O(v^2 log v + ve). This is the standard all pair shortest problem, As I only need one vertex (s) - my time complexity will be O(v log v + e) right?

Answer 1

For this kind of problem, changing the graph is often a lot easier than changing the algorithm. Let's call the two negative-weight edges N1 and N2; a path by definition cannot use the same edge more than once, so there are four kinds of path:

• A. Those which use neither N1 nor N2,
• B. Those which use N1 but not N2,
• C. Those which use N2 but not N1,
• D. Those which use both N1 and N2.

So we can construct a new graph with four copies of each node from the original graph, such that for each node u in the original graph, (u, A), (u, B), (u, C) and (u, D) are nodes in the new graph. The edges in the new graph are as follows:

• For each positive weight edge u-v in the original graph, there are four copies of this edge in the new graph, (u, A)-(v, A) ... (u, D)-(v, D). Each edge in the new graph has the same weight as the corresponding edge in the original graph.
• For the first negative-weight edge (N1), there are two copies of this edge in the new graph; one from layer A to layer B, and one from layer C to layer D. These new edges have weight 0.
• For the second negative-weight edge (N2), there are two copies of this edge in the new graph; one from layer A to layer C, and one from layer B to layer D. These new edges have weight 0.

Now we can run any standard single-source shortest-path problem, e.g. Dijkstra's algorithm, just once on the new graph. The shortest path from the source to a node u in the original graph will be one of the following four paths in the new graph, whichever corresponds to a path of the lowest weight in the original graph:

• (source, A) to (u, A) with the same weight.
• (source, A) to (u, B) with the weight in the new graph minus the weight of N1.
• (source, A) to (u, C) with the weight in the new graph minus the weight of N2.
• (source, A) to (u, D) with the weight in the new graph minus the weights of N1 and N2.

Since the new graph has 4V vertices and 4E - 2 edges, the worst-case performance of Dijkstra's algorithm is O((4E - 2) + 4V log 4V), which simplifies to O(E + V log V) as required.

To ensure that a shortest path in the new graph corresponds to a genuine path in the original graph, it remains to be proved that a path from e.g. (source, A) to (u, B) will not use two copies of the same edge from the original graph. That is quite easy to show, but I'll leave it to you as something to think about.