The motivation for this question is a statement about the Bellman-Ford algorithm, that doesn't agree with the definition of what a [path](https://mathworld.wolfram.com/PathGraph.html) in a graph is.


On wikipedia's description of the [Bellman-Ford Algorithm](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_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"
> 
> 
> 


because



> 
> "any path that has a point on the negative cycle can be made cheaper by one more *walk* around the negative cycle."
> 
> 
> 


  

**Questions:**


* In view of the definition of [paths](https://mathworld.wolfram.com/GraphPath.html) is it formally correct to speak of "shortest-path" algorithms if they actually calculate shortest [walk](https://mathworld.wolfram.com/Walk.html)s, 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)?



What do shortest-path algorithms actually calculate?
Computer Science often (usually, in my experience) defines a *path* as a sequence of vertices with edges between them, i.e. what others call a *walk*. E.g. on my shelf, this definition appears in *Algorithm Design* by Kleinberg and Tardos, *Introduction to Algorithms* by CLRS, and *AI: A Modern Approach* by Russell and Norvig. If there are no repeated vertices or edges, this terminology would call it a *simple path*. So "Shortest Paths" algorithms refers to this definition.


In your terminology: one could say these algorithms find shortest walks, not shortest paths, but the only case where the two are different is when there is a negative cycle, where no shortest walk exists and finding the shortest path is NP-hard as aorq points out.


