Find the Longest Path
Find the Longest Path

I need to find the longest path in the graph based on edge weights. For the graph on image it should be 4,5,3,2,1 (order doesn’t matter) What is the best algorithm to solve this? What if you know that in your graph, every node has a reference(edge) to any other node in the graph. Should the algorithm be changed?

• 1Have you already looked at en.wikipedia.org/wiki/Longest_path_problem?– SaiBotMar 4, 2019 at 8:13
• @SaiBot yes, sure. “In weighted complete graphs with non-negative edge weights, the weighted longest path problem is the same as the Travelling salesman path problem, because the longest path always includes all vertices.” I din’t understand how TSP can help me here. Can you point me what section of the wiki article is relevant to my problem pls? Mar 4, 2019 at 8:56
• 1Ok good, so you understand that the problem cannot be solved efficiently (as molamk also explained in his answer). That means if your graph is large you will have to go for an approximate solution. If you graph is fully connected you can transform the problem into TSP by inverting the edge weights (e.g., new_edge_weight = max_edge_weight – old_edge_weight). There are many good approximate (heuristic) approaches for TSP that you can utilize then.– SaiBotMar 4, 2019 at 9:05