I came across a problem where I have to find out the longest path in a given graph. I have list of edges ( eg.{AB, BC} ) which states there is an edge between vertices/nodes (A,B,C). Now i want to figure out the longest path possible (not repeating the vertex) such that it covers maximum nodes starting from any vertex/node.
What can be the best way to solve this? I have to implement this as a program.
I looked up google for Minimum Spanning Tree, Dijkstra's Alogorithms , hamiltonain path( which i think suits- but not sure ) and many more. but can't figure out what would suit best for this problem.
Any help or reading references would be much appreciated.
Best Answer
See http://en.wikipedia.org/wiki/Longest_path_problem for a discussion of the longest path problem. In general it is NP-hard unless your graph is directed acyclic. Thus there are probably no fast solutions. If you want a somewhat brute force solution, then for each starting node do a depth first search (look up on wikipedia if you're not familiar with it) where you keep track of all the vertices on the current path you are traversing and do not allow repeated vertices, and if you find a path longer than the current longest path found so far then store the current longest path. This has exponential worst case time complexity for an arbitrary graph but low memory use, so it should run just fine if you are willing to wait long enough.