The motivation for this question is a statement about the Bellman-Ford algorithm, that doesn't agree with the definition of what a path in a graph is.
On wikipedia's description of the Bellman-Ford Algorithm it is stated that:
"If a graph contains a "negative cycle" (i.e. a cycle whose edges sum to a negative value) that is reachable from the source, then there is no cheapest path"
"any path that has a point on the negative cycle can be made cheaper by one more walk around the negative cycle."
- In view of the definition of paths is it formally correct to speak of "shortest-path" algorithms if they actually calculate shortest walks, i.e. whether or not the walk happens to be a path depends on the edge weights?
- Are any efficient genuine shortest path algorithms known that are immune to the presence of negative cycles (remembr: in a finite graph with finite edge weights there are no paths with unbounded negative length)?