Dijkstra's Shortest-Path Algorithm I'm presented with the following algorithm:


Dijkstra's Shortest-Path Algorithm
This algorithm finds the length of a shortest path from veftex $a$ to vertex $z$ in a connected, weighted graph. The weight of edge $(i,j)$ is such that $w(i,j)>0$, and the label of vertex $x$ is $L(x)$. At termination, $L(z)$ is the length of a shortest path from $a$ to $z$.
$\hspace{1cm}$Input: A connected, weighted graph in which all weights are positive; vertices $a$ and $z$
$\hspace{1cm}$Output: $L(z)$, the length of a shortest path from $a$ to $z$
1$\hspace{0.75cm}$dijkstra(w,a,z,L){
2$\hspace{0.75cm}$   L(a)=0
3$\hspace{0.75cm}$   for all vertices x$\neq$a
4$\hspace{0.75cm}$      L(x)=$\infty$
5$\hspace{0.75cm}$   T = set of all vertices
6$\hspace{0.75cm}$   //T is the set of vertices whose shortest distance from a has
7$\hspace{0.75cm}$   //not been found
8$\hspace{0.75cm}$   while(z$\in$T){
9$\hspace{0.75cm}$      chose v$\in$T with minimum L(v)
10$\hspace{0.75cm}$      T=T-{v}
11$\hspace{0.75cm}$      for each x$\in$T adjacent to v
12$\hspace{0.75cm}$         L(x)=min{L(x),L(v)+w(v,x)}
13$\hspace{0.75cm}$   }
14$\hspace{0.75cm}$}


I'm then asked the following question:


True or false? This algorithm finds the length of the shortest path in a connected, weighted graph even if some weights are negative. If true, prove it; otherwise, provide a counter example.


My question is what is being communicated in this algorithm?
 A: I'm not sure I completely get the question -- you are having trouble understanding Dijkstra's algorithm? The Wikipedia article is good, and there are many nice worked examples on the web. I would try to work through some of these examples, and then ask specific questions if you're still confused about how the algorithm works.
As for the homework problem you've quoted, here's a hint: any algorithm, Dijkstra or otherwise, for finding a shortest path will only work if such a path actually exists. Can you come up with an example of a connected weighted graph where no shortest path exists between some pair of nodes?
A: The question is a bit ambiguous, due to nonstandardized notation. The question is: can a path consist of repeated vertices and/or edges? Some authors say yes (and, when no, they call it a simple path), while others say no (and, when yes, they call it a walk instead of a path). More on that on Wikipedia.
If your path can have repetitions, then see what happens with the graph that has a cycle with (total) negative weight, and tell us what you got. Otherwise, I see no difference between edges with negative and nonnegative weights.
A: Actually, Dijkstra's Algorithm does not work for negative weights. There is an easy counterexample for that: 
Let the set of vertices $V = {a, z, x}$ and the set of edges $A = {(a, x), (a, z), (x, z)}$. Now consider the weight function which is defined such that $w((a, x)) = 10$, $w((a, z)) = 5$, $w((x, z)) = -10$. 
You might want to draw this to see why here we do not actually find the correct shortest path from vertex $a$ to vertex $z$ using Dijkstra's Algorithm. The set $T$ consists only of $a$ in the beginning. $L(z) = 5$ and $L(x) = 10$ at this point. So in the next step of the algorithm we add $z$ to the set $T$ and return that the shortest path from $a$ to $z$ is of length $5$. But this is not true, since the path $a, x, z$ has length 0.
