Dijkstra Algorithm with all negative weights

Question

Let's assume that I have a graph G and all of the edges in G have negative weights without negative cycle.

If I run this by Dijkstra Algorithm, will it find a shortest path?

Thanks

Does this answer your question? [Why doesn't Dijkstra's algorithm work for negative weight edges?](https://stackoverflow.com/questions/13159337/why-doesnt-dijkstras-algorithm-work-for-negative-weight-edges) — Peter, May 02 '20 at 06:28

h3yduck · Answer 1 · 2020-01-01T19:24:30.447

0

I think it won't. There is a similar question with answer here: Why doesn't Dijkstra's algorithm work for negative weight edges?.

The only difference between your question and that one is that your graph doesn't have positive edges at all. Still, i.e. in this graph:

       A
      / \
     /   \
    /     \
  -2       -5
  <         >
  B--(-10)-->C

If the algorithm starts from A it will find A->C as shortest path to C (where the shortest path is actually A->B->C).

EDIT: Directed edges are: (A,C,-5), (A,B,-2), (B,C,-10)

edited Jan 01 '20 at 19:24

answered Dec 30 '19 at 12:44

h3yduck

1,571
14
14

Yes I agree with you however I asked about a case that the graph doesn't have a negative cycle. Like @AbcAeffchen said, I think the algorithm will find the shortest path? – jjpark Jan 01 '20 at 17:31
I edited my answer. It doesn't have a negative circle but It won't find the right path from `A` to `C`. It will select `A->C` as the shortest path at first step with a distance of `-5`, where the shortest distance is actually through `A->B->C` with a distance of `-12`. – h3yduck Jan 01 '20 at 19:26
It will only work if your graph is actually a tree without multiple possible paths as @AbcAeffchen said. – h3yduck Jan 01 '20 at 19:29

score 0 · Answer 2 · answered Dec 30 '19 at 13:54

If the graph is undirected, with only negative edge weights and without cycles, then the graph is a tree and there it should work. At least as long as you look for simple paths, without going back and forth over and over again. E.g. A---B---C all weights are -1. Then the shortest simple path from A to C would be A,B,C, but if you drop the simple restriction, then there is no shortest path anymore. Instead it would look like this A,B,A,B,A,B, ... ,C.

If your graph is directed, the example from @h3yduck can be made directed and is a counterexample that shows that Dijkstras Algorithm does not work in this case.

Dijkstra Algorithm with all negative weights

2 Answers2