If you apply standard Bellman-Ford algorithm to a graph containing negative loop it can only report its existence. Are there approaches to modify it to find shortest path containing any vertex not more than once so effectively avoiding loops? I would appreciate if an answer will contain a link to a paper.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
As far as we know, you can't. The problem of finding the shortest simple path in a graph is NP-hard; it is equivalent to the problem of finding the longest simple path (just negate all edge lengths), which is at least as hard as Hamiltonian path, which is NP-hard. Therefore you shouldn't any simple modification to Bellman-Ford to yield an efficient algorithm for this problem; best guess right now is that no such algorithm exists.
See also https://cstheory.stackexchange.com/q/17462/5038 and https://en.wikipedia.org/wiki/Longest_path_problem. According to Wikipedia, the longest path problem is fixed-parameter tractable and can be solved in time exponential in the length of the longest path and linear in the size of the graph, which also applies to your problem as well.
-
$\begingroup$ Surprisingly this answer has everything to solve my real problem. Wikipedia says that longest path problem can be solved in time linear in the size of the input graph but exponential in the length of the path. And I'm quite OK with additional constraint on path length. So thank you! Maybe it is worth to add it as a note to your answer? $\endgroup$ Commented Feb 12, 2018 at 17:58
-
$\begingroup$ @IgorMikushkin, glad it helped! Good idea -- I've added that to my answer. $\endgroup$– D.W. ♦Commented Feb 12, 2018 at 19:08