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?
$\begingroup$
$\endgroup$
2
-
$\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. ♦Commented 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. ♦Commented Mar 4, 2021 at 7:04
Add a comment
|