Understanding the Longest Path Problem and the Bellmanford Act

"The ""longest path problem"" that involves NP integrity refers to the problem of finding the longest simple path (simple path, path with no overlapping vertices) in a weighted directed graph."On the other hand, the shortest route problem, such as the Bellman-Ford method, solves the problem of finding the shortest route.Considering that you want a simple road instead of a road, you can see that -1 times the weight of the side is not enough.

Also, if you are thinking about finding the longest path rather than the longest simple path, you can get to the shortest path problem by multiplying the weight by -1.In this case, if the original graph has a regular closure path that can be reached from the starting point, the length can be increased indefinitely, so there is no solution.