1

how can I get longest path in unweighted undirected graph if each node can be visited only once? Thanks for help! // I am new to graphs.I've found out that each edge can be visited only once,not node.Node can be visited more times.Does it mean that my graph is directed? Thanks

Flash
  • 11
  • 2

1 Answers1

2

This is obviously an NP-complete problem, as Hamiltonian path problem can be reduced to this one. So you will most probably have no polynomial solution here. For non-polynomial you can just use brute force, or try to adapt numerous Hamiltonian path approaches.

Petr
  • 9,812
  • 1
  • 28
  • 52
  • You sure this is NP-complete? Can you elaborate a little how Hamiltonian path can be reduced to diameter of graph? – vish4071 Nov 11 '15 at 14:30
  • @vish4071 The diameter of a graph is the longest *shortest* path. OP asks for the longest path. Those problems are completely unrelated. – Vincent van der Weele Nov 11 '15 at 14:33
  • 1
    @vish4071, assume we need to solve Hamiltonian path on a graph. Let's instead solve the OP's problem: find the longest path which visits each vertex at most once. If this path visits _every_ vertex, it is Hamiltonian. Otherwise, it is obvious no Hamiltonian path exists, as if it existed, it would make a better solution for OP's problem. – Petr Nov 11 '15 at 14:34
  • @VincentvanderWeele, you have wrong idea of diameter. It is defined as "longest distance between 2 nodes in a graph", which is obvs what OP is asking. – vish4071 Nov 11 '15 at 14:38
  • @vish4071 right, where "distance between 2 nodes" is defined as the shortest distance... see for instance [wolfram](http://mathworld.wolfram.com/GraphDiameter.html). – Vincent van der Weele Nov 11 '15 at 14:41
  • @Petr, but here we do not have to visit each vertex. Its just that, if we start with a vertex and do BFS, then, the last level will tell us the length of diameter (if this node is one of the end points of diameter of course). So, doing BFS from each node gives us the length in O((v+e)*v) as we are doing BFS `v` times. Some modification in this should give diameter itself. – vish4071 Nov 11 '15 at 14:42
  • @vish4071, consider a simple triangle graph -- three vertices, three edges. The answer to OP's question will be path of 2 edges, 3 vertices, while your algorithm will just find path of 1 edge, 2 vertices. – Petr Nov 11 '15 at 15:21