If every nontrivial closed subwalk has strictly positive weight, removing any repeated-vertex segment strictly decreases a walk's weight. Hence a minimum-weight walk must be a graph path, and it is a shortest path. Strictly positive edge weights are sufficient in an undirected graph. For a trail, positivity of every simple cycle is already sufficient: its first repeated-vertex segment is a cycle because no edge is repeated.
Under the usual unrestricted walk convention, positivity of simple cycles alone is insufficient. A graph consisting of one zero-weight edge has no cycles, but the walk is a minimum-weight walk and is not a path. A zero-weight backtrack cannot be removed with a strict improvement. For nonnegative edge weights, one may erase such backtracks without increasing weight and obtain a shortest path, but cannot conclude that every minimum walk was already a path.

Articles by others on the same topic (0)

There are currently no matching articles.