How to Find the Longest Path with Negative Weights
Asked 2 years ago, Updated 2 years ago, 81 viewsWe would like to receive your ideas.
For business purposes, I would like to find the longest path to the directed graph as shown below.
I am thinking about it.①From to まで.
The actual graph is more complicated, so it's hard to get round.
At first, I thought about using the Dijkstra method, but
①The Dijkstra method determines the minimum path, so it is the longest path
There is no need for
②It has a negative weight.
So I gave up.
How to solve this problem successfully by the Dijkstra method or by the Dijkstra method
Is there any way to solve this problem, not limited to ?
2 Answers
https://en.wikipedia.org/wiki/Longest_path_problem
Even if there is no negative weight, the longest route problem is generally NP-difficult, so I think the only solution is to win.
For some of the longest route problems in special cases (e.g., graphs without loops), methods to avoid NP difficulties seem to have been found (mjy says, using a graph that reverses the positive and negative weights), but I don't think this graph has such properties at least.
If I were to actually deal with it at work, I would have to think of a way to avoid solving the longest route problem.
Thank you all for your reply.I will use it as a reference.
After reviewing the problem, we decided to DAGize it to find a value that is close to the longest path.
If you have any answers or tips
© 2024 OneMinuteCode. All rights reserved.