# extending bellman ford to find shortest weight paths with no repeating vertices

Is it possible to extend the Bellman Ford algorithm to output all shortest simple paths without repeating vertices?

The issue is that the Bellman Ford algorithm doesn't make any checks for whether the shortest "paths" it counts have repeating vertices. Also, if one were to keep track of all of these paths, I think it would be very inefficient. Breadth first search doesn't even come close to solving the issue, as it can't be used if edge weights are not all equal to a positive number. Dijkstra's algorithm doesn't work for negative weight edges.

Note: Unlike in the Bellman ford algorithm, negative weight cycles are allowed; since each vertex in a shortest simple path must be distinct, a shortest simple path must always exist.

• Could you try writing an answer that shows finding shortest weight paths with no repeating vertices is at least as hard as Hamiltonian path problem. Hint, consider giving every edge of an unweighted graph weight $-1$. Mar 19 at 20:28