Can someone help me with this question
I am still confused weather Dijkstra's algorithm works with negative edges or not
this question is from Grokking Algorithms book and in its errata it is said that this question has a possible answer
how does it has a possible answer with a negative edge?

CodePudding user response：

First of all Dijkstra's algorithm won't work on all negative weighted graphs, but on this particular case you can see that the negative weight not make any different on the shortest way to get from the starting point to any other point on the graph. this is why you will get the same result with the negative edge or without.

The idea why Dijkstra's won't work on negative weighted graphs is explained pretty well here (thanks to Amit) -> Why doesn't Dijkstra's algorithm work for negative weight edges?

CodePudding user response：

It's been literally 10 years since I last touched anything to do with Dijkstra, but I think this one doesn't break because every time you pass over the negative portion, the loop still increases the sum (minus 1 vs several plus 2). This way, the path with the negative is discarded. But change that minus 1 to minus 5 and then you have a problem.

I'm not on my PC right now to apply this graph to my 10 year old homework, but I'm pretty sure that's what's going on.