CODEWITHSUNDEEP
algorithmgraph
praveen
praveen

Reputation: 3263

Algorithm to find a linear path of minimum weight in a graph that connects all the vertices exactly once

Given a weighted undirected graph with n vertices, I face the problem of finding a path of minimum weight that connects each of the vertices in a line. At first, I thought this is the problem of finding the minimum spanning tree but this is not the case. In case of a spanning tree, there may be branches at a vertex or the degree may be greater than two. What I need to find is a linear path i.e all the vertices except the end vertices have degree exactly two. The start and end vertex can be any of the n vertices.

Mine was a greedy approach i.e

first chose any vertex, maintain a sum 
    check all its neighbors such that the cost of reaching it is 
    least among all the neighbors
    mark this neighbor as visited
    add the cost to sum
repeat the procedure above until all the points have been visited.

I will have to do this for all the vertices as the starting point. I am not sure if this algorithm is correct and also its complexity is high. What should be the better approach to this problem?

Upvotes: 3

Views: 4603

Answers (2)

Jerry Coffin
Jerry Coffin

Reputation: 490148

While I think @templatetypedef is correct and this is really an instance of the Hamiltonian Path problem, you'll probably get better results by Googling for traveling salesman problem -- it's close enough that most (all?) TSP heuristics will work for you as well (the sole difference is that TSP is at least normally described as adding a path from the end back to the beginning, so it forms a "ring" instead of just a line). TSP also typically assumes a complete graph (i.e., every node connects to every other); if your graph isn't complete, you can still use the normal algorithms by adding a connection of infinite weight between any unconnected nodes.

The greedy approach you've given is generally known as the "nearest neighbor" heuristic. It's the first approach that occurs to nearly everybody. Its producing non-optimal solutions has been known for over a century. Unfortunately, anything else that runs in reasonable time will also have at least the possibility of producing sub-optimal solutions as well (at least in the absence of restrictions on the problem). A* is probably the most common algorithm for producing reasonable (only slightly suboptimal) results in reasonable time.

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372814

This problem is known to be NP-hard by a reduction from the Hamiltonian path problem, since if you give all the edges weight 1 and ask "is there a linear path of weight at most n?" then the answer is "yes" precisely if the graph contains a Hamiltonian path. As a result, you are unlikely to find an algorithm that works better than pure brute force, since unless P = NP there are no polynomial-time solutions.

Sorry to rain in on your parade, and hope this helps!

Upvotes: 7

Related Questions