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
    Commented May 24, 2021 at 17:53
  • 1
    $\begingroup$ Search phrase: "elementary shortest path" $\endgroup$
    – RobPratt
    Commented 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
    Commented May 25, 2021 at 13:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .