0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – John L.
    Mar 19, 2022 at 20:28

1 Answer 1

Reset to default
1
$\begingroup$

There won't be repeating vertices. If there was one, then there must have been a negative cycle that it is a part of - since otherwise (the cycle's weight is positive) you can "remove" the entire cycle and by that reduce the total path's weight, hence contradicting the fact that the original path was optimal.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. So, if possible, could you elaborate on what would happen if there was a negative weight cycle? $\endgroup$
    – Fred Jefferson
    Mar 18, 2022 at 17:42
  • $\begingroup$ The bellman-ford algorithm detects negative weight cycles, so if there was one - the bellman ford will not output a "minimal path" (since there isn't one), and instead will output "there is a negative cycle in the graph". $\endgroup$
    – nir shahar
    Mar 18, 2022 at 17:43
  • $\begingroup$ Yes, but I'm pretty sure that if all vertices must be distinct, then there always exists a minimal weight path, even if the graph has a negative cycle. So in that sense, the Bellman ford algorithm might not work. Though I guess I should've clarified in the question that I explicitly allow the case where the graph has negative cycles. $\endgroup$
    – Fred Jefferson
    Mar 19, 2022 at 18:46
  • $\begingroup$ You are right. In the case of allowing negative cycles by constraining the paths to be vertex-distinct, then the bellman-ford algorithm might not be correct (since it just "gives up" when it detects negative cycles). Bellman-ford will be intrinsically problematic in this case, since it can't detect negative cycles until its very last iteration - where then it is already too late. So I think you will have to come up with a totally different algorithm for this case... I think there is an algorithm for this case when the weights are integers $\endgroup$
    – nir shahar
    Mar 19, 2022 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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