I am reading "Introduction to Algorithms 3rd Edition" by CLRS.
There are the following sentences in this book:
The Bellman-Ford algorithm solves the single-source shortest-paths problem in
the general case in which edge weights may be negative. Given a weighted, directed graph $G = (V, E)$ with source $s$ and weight function $w : E \to \mathbb{R}$, the
Bellman-Ford algorithm returns a boolean value indicating whether or not there is
a negative-weight cycle that is reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists.
I think maybe there is a solution for some vertex $v$ even if there is a negative-weight cycle that is reachable from the source.
Please see the above picture.
There is a solution for $v$ and $\delta(s, v) = 5$.
Why does this algorithm give up finding the distance from $s$ to $v$?
Best Answer
Bellman-Ford computes the shortest path from the "source" $s$ to all other vertices. If there's some vertex $k$ for which $d(s, v)$ is undefined (because of a negative-weight cycle, for instance), then the problem is unsolvable, because a solution consists of shortest paths to all vertices. In your example, there's no shortest path from $s$ to the topmost vertex, as running around the triangle multiple times can always "shorten" the path.