Negative edge weights in Dijkstra

Question

All text books and online resources say 

Dijkstra's algorithm need all non negative edge weights

However I feel a bit different, especially after coming across problem asking to build shortest path tree from node aa in following graph:

My shortest path tree after running Dijkstra came like this:

Then why texts say that Dijkstra need all non negative edge weights? I feel that it should be no -ve edge weight cycle reachable from source node. Am I correct with this? or am I missing something here?

Comments

Yes Dijkstra may be work if there is negative weight edge but won't work if negative edge cycle is present.

---

then why books say "all non negative edges"? especially coreman too!!! snap from coreman:

---

added snap from coreman to the above comment...

---

Dijkstra will definitely work for all non negative edges and may or may not work for other cases like -ve edge weights or -ve edge cycles.

---

yeah it is not meant for -ve edges but it may work. like for this question

https://gateoverflow.in/457/gate2008-45

---

I think Dijkstra will give wrong answer to above graph.So negative edges are undesired.

---

So does it work for all graphs with negative edges having no cycle with negative edge? For example, does it work for below graph? I am getting red colored edges as shortest path tree.

---

@Ajay Jadhav 
why will it give wrong answer for your graph?
I am getting this:

First it will add AB, then AC, then CD. RIght?
If yes, then will Dijkstra work for all graphs with -ve edges but no negative edge cycle reachable from source?

---

It does not give any assurance as whether it will give the correct result in case of graphs with -ve edge weights. It may or may not give.

And yes.. red path is correct.

---

I guess only counter example can satisfy me and I am absolutely not able to come up with the counter example for the fact:

Dijkstra "always" works as long as there is -ve and / or +ve edge (that is may or may not contain both) path reachable from source, but not -ve edge cycle.

Reading pseudo code of Dijkstra from Coreman, I dont feel there is any line of code which causes above fact to fail:

Can you please at least tell me which line may fail on -ve edge? Or Can you pleaseee given me counter example (cause am afraid even if you point me to some line in code, I will still make it work for any graph , if I am having some deep false understanding about working of all those pseudocode lines, which I believe I do have )? That is

example of graph with -ve edge and no -ve edge cycle but Dijkstra is failing on it in some way.

Just to note
Below snip is from coreman stated at the start of the chapter, before Dijhstra section. Dont know if it applies to Dijkstra:

 

---

https://youtu.be/2raV0H9KqY8

You wanted an example..here it is.. watch from 12:00 

---

daaaamn maan...
So below is the fact I was indeed missing !!!???

shortest path tree will be formed in all graphs without -ve edge cycles (even though they might have -ve edges), but might be that a node will get relaxed after it has been extracted from Q (as per CLRS algo, which means node has been added to the shortest path tree) which is considered wrong in Dijkstra.

Right?!??!?!

---

I have not yet convinced that dijkstra algorithm breaks for graph with $-$ve edge weights. So went forward and tried out the code.

I have taken C code for dijkstra from geeksforgeeks page and applied it to below graph:

graph on ideone here. 
Also applied to graph obtained by swapping weights 1 & 4:

on ideone here. They both work even though there is -ve weight $-3$ edge. 
Can you please have a look at this?

Answer 1

GRAPH WITH ONLY POSITIVE WT: Dijkstra will work fine

GRAPH WITH NEGATIVE WT EDGES BUT NO NEGATIVE WT CYCLE: Dijkstra may or may not fail

GRAPH WITH NEGATIVE WT CYCLE: Dijkstra surely fails

Why Dijstra will work in -ve edges ?.
It may fail in -ve edge even there is no -ve cycle.

Can u calculate distance from A to C using Dijkstra ?, It will be 2, right ?
But actual shortest distance is 1 only. (Here Dijkstra fails even NO cycle.)

Here whats happening, Observe:-

Dijkstra had 2 choices to go to C from A, It chooses direct path.
It says if I go via B, then i would have to incur ATLEAST 5 cost. (it don't know that in future there may be a -ve edge.)
It thinks, A to B distance itself is 5 and if I go via B then cost would always increase, there is no chance of decrease. but to his surprise I put "-4"

Actually Dijkstra assumes that all edges are +ve. (if u see proof of " correctness of Dijkstra" then first assumption is weights are +ve )