I understand that the Bellman-Ford Algorithm can solve the single-source shortest-paths problem. However, can it also be used to determine the longest path in an undirected, graph through first negating the weight of all the edges?
Can the Bellman-Ford Algorithm be used to find the longest path in an undirected graph through first negating the weight of all the edges? [duplicate]
Modified 2 years ago
Viewed 37 times
$\begingroup$ cs.stackexchange.com/q/17980/755, cs.stackexchange.com/q/57894/755, cs.stackexchange.com/q/88003/755, cs.stackexchange.com/q/2660/755, cs.stackexchange.com/q/125264/755 $\endgroup$– D.W. ♦Mar 4, 2021 at 7:03
$\begingroup$ You'll need to define what you mean by "longest path". Does it have to be a simple path? Do you allow visiting the same vertex/edge more than once? In the future I encourage you to spend some time searching the site before asking; we have many prior questions that cover the longest path problem here. See meta.stackoverflow.com/q/261592/781723. $\endgroup$– D.W. ♦Mar 4, 2021 at 7:04
Add a comment |