2

So I've been working with Dijkstra's algorithm and directed graphs a lot lately. However, I can't seem to figure this out and it's really starting to bother me.

Show how to modify Dijkstra’s algorithm to solve the single source shortest path problem if there is exactly one negative weight edge but no negative weight cycles.

So far my initial thought has been to somehow split up the graphs and perform the algorithm separately, but that's about all I've thought of.

I've actually found an explanation I'm looking for, but I can't seem to follow his explanation

Well answered! I'd like to point out that if the number of negative edges is limited, there are Dijkstra-based algorithms that might do a better job. For example, if there is only one negative edge from u to v, you could run Dijkstra on s and on v, and then take the minimum for each vertex between d[s] and d[s]+w(u, v)+d[v], giving a complexity of running Dijkstra twice

Community
  • 1
  • 1
Jake Senior
  • 223
  • 4
  • 11
  • possible duplicate of [Dijkstra's algorithm with negative weights](http://stackoverflow.com/questions/5956534/dijkstras-algorithm-with-negative-weights) – orlp Apr 29 '15 at 00:05
  • 1
    @orlp that thread just refers to the Bellman-Ford method. That's a different algorithm. I'm looking to modify the Dijkstra's algorithm and have it work on a graph with a single negative edge. – Jake Senior Apr 29 '15 at 00:12
  • Why can't we just increase all the edge weights with the most negative number and apply Dijkstra's ?? – Dunes Buggy Apr 29 '15 at 00:14
  • @iRaviiVooda Consider the graph where there are two paths from A to B, one traversing a single edge of length 2, and one traversing edges of length 1, 1, and -2. The second path is shorter, but if you increase all edge weights by 2, the first path now has length 4, and the second path has length 6, reversing the shortest paths. This tactic will only work if all possible paths between the two points use the same number of edges. – Jake Senior Apr 29 '15 at 00:15
  • 1
    _"because couldn't the algorithm just constantly loop over the negative edge to negative infinity in some cases?"_ - no, because there are _"no negative weight cycles"_ – Eric Apr 29 '15 at 00:23
  • People here seem to only read the title, so I edited it to make their job easier. – Juan Lopes Apr 29 '15 at 00:24
  • 1
    Just spitballing here: Considering that there's exactly one negative weight edge *and* no negative weight cycles, could you perform an initial dijkstra on the graph, replacing the negative weight edge with 0. Afterwards, you could reset the edge to negative and propagate out from the node the edge extends from? If I could prove this as an answer, I would have posted it as such. For now, it's relegated to conjecture in the comments. – AndyG Apr 29 '15 at 00:25

1 Answers1

7

Remove the negative edge (u, v), run Dijkstra twice: once starting at s (D1) and once starting at v (D2)

The shortest path between s and t is: min(D1[t], D1[u]+D2[t]+w(u, v)).

Juan Lopes
  • 10,143
  • 2
  • 25
  • 44