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

2 Answers

  • The longest path problem is NP-complete which means that it cannot be solved in polynomial time.
  • For directed acyclic graphs it has a linear solution, but since the question is about undirected graphs, that won’t work.
  • A “valid” solution can be to simply brute-force the graph by traversing in a depth-first manner multiple times in order to generate all possible paths from A to B. When you have generated all paths, find the one with the maximum distance.

Finding the longest path in a graph is an NP-Complete problem. Contrary to popular belief, this does not mean that it cannot be solved in polynomial time (in fact this is one of the great unsolved problems in computer science P vs NP). However, it does mean that it is at least as hard as the hardest problems in NP. In other words, there may be an efficient algorithm to solve this problem, but no one so far has been able to find it. In effect it is impossible to solve efficiently. Knowing that every node has an edge to every other node does not change the fact that this problem is NP-complete.

You are watching: Longest Path in a weighed non directed graph. Info created by GBee English Center selection and synthesis along with other related topics.