# What do shortest-path algorithms actually calculate?

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"

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 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)?
• If you have a graph $G$ with $n$ vertices and you assign a weight of $-1$ to each edge, the shortest true path from $u$ to $v$ has weight $-(n-1)$ if and only if there is a Hamiltonian path from $u$ to $v$. Thus your second question is a Millennium Prize Problem! ☺️
– aorq
May 24 at 17:53
• Search phrase: "elementary shortest path" May 24 at 18:46