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
|