Answer to Problem 2

Answer (and important discussion)

If you read our definition of distance carefully, you will realize that the answer is:



Equation 4

This is because there exists a path from to containing a cycle of negative weight (see below).



Figure 6:

The indicated cycle has negative length.



So, for some weighted graphs, there exist walks from a vertex to another vertex, but none of them is a shortest walk.

Such a situation is not desirable, and, in practice, must be avoided. The best way to avoid the above situation is to prohibit graphs from having cycles of negative weight. (Notice that this restriction still allows the existence of individual edges of negative length).

Proposition

If the length of every cycle in a graph is positive, then a shortest walk between two vertices is a path.