Why does Dijkstra's algorithm fail on a negative weighted graphs?

Question Detail: 

I know this is probably very basic, I just can't wrap my head around it.
We recently studied about Dijkstra's algorithm for finding the shortest path between two vertices on a weighted graph.
My professor said this algorithm will not work on a graph with negative edges, so I tried to figure out what could be wrong with shifting all the edges weights by a positive number, so that they all be positive, when the input graph has negative edges in it.
For example, let's consider the following input graph:

Now if I'll add 3 to all edges, it's obvious that the shortest path (between $s$ and $t$) has changed:
Thus this kind of operation might result in wrong output. And this, basically, what I don't get. Why does this happen? Why is shifting the values has such a dramatic effect on the shortest path? This is totally counter-intuitive, at least for me.
In probability, when you have some (discrete) distribution probability given by some random variable $X$, and you want to calculate the variance, then for every constant $c$, it holds that $Var(X+c)=Var(X)$, and this happens, of-course, because shifting the distribution values left or right does not effect how $X$ spreads.
Now, I'm well aware that these are two different things here, and finding the shortest path is not exactly the same as calculating the variance of a random distribution function, but I'm just saying that this is why to me it seems so counter-intuitive.

Your thoughts?

Asked By : so.very.tired

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19771

Answered By : Raphael

Dijkstra relies on one "simple" fact: if all weights are non-negative, adding an edge can never make a path shorter. That's why picking the shortest candidate edge (local optimality) always ends up being correct (global optimality).

If that is not the case, the "frontier" of candidate edges does not send the right signals; a cheap edge might lure you down a path with positive weights while an expensive one hides a path with negative weights.

For details, I recommend you check out a correctness proof and try to do it with negative weights; observe where it breaks.