2
$\begingroup$

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)?
Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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! ☺️ $\endgroup$
    – aorq
    May 24, 2021 at 17:53
  • 1
    $\begingroup$ Search phrase: "elementary shortest path" $\endgroup$
    – RobPratt
    May 24, 2021 at 18:46

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Maybe there is a need for "standardization" of certain terms that would allow for their use without further explanation. $\endgroup$
    – Manfred Weis
    May 25, 2021 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.