Shortest path visiting set of vertices in an un directed graph

2
votes

I have an undirected graph of locations in an indoor map. When given a set of vertices , i want to find the shortest path which will cover all those vertices. Graph contains 52 vertices and 150 - 250 Edges.

What is the best algorithm i can use to find the shortest path. Please don't get confused that this is a Travelling Salesman Problem. It doesn't have to cover all the nodes.Only the given set of nodes.

1
algorithmgraphgraph-theorygraph-algorithm
This is just a form of TSP for that smaller set of nodes. It may even have a greater complexity than TSP. - RBarryYoung
Well, if you're looking for a general algorithm, then consider that this algorithm will have to deal with solving this problem when all the nodes are required. which is equivalent to the Minimum Weight Hamiltonian Path Problem (not the TSP), which is a hard problem. - Ron Teller
@RonTeller,Is there an algorithm for "the Minimum Weight Hamiltonian Path Problem" ? - direndd
@DirenDantanarayana That's an NP-hard problem, so nothing efficient is known. - G. Bach
I am not looking for efficient ones. I just want the algorithm. Efficiency is not an issue. :) - direndd

1 Answers

1
votes

As i've commented, this is a hard problem, so don't expect a polynomial time algorithm.

But if you're looking for an algorithm that you may be able to compute in acceptable time for the problem instances you mentioned, this might work:

Let G(V,E) be the original graph, let N be the set of nodes that must be visited.

1. Compute the shortest-path matrix M for the entire graph (|V|x|V| matrix that contains
   the length of the shortest path between each two nodes).
2. Generate a new graph G`, containing N alone, with the distances between each 
   two nodes taken from the shortest-path matrix M.
3. Solve the Minimum Weight Hamiltonian Path Problem on G`.

Note that the "hardest" part here is the third part, which takes exponential time. but if the group N is not too big, you'll be able to solve it:

  • Bruteforce algorithm will let you solve problems where N contains about 11 nodes within seconds ( O(|N|!) complexity )
  • Dynamic Programming will let you solve problems where N contains about 20 nodes within seconds ( O(2^|N|*|N|^2) complexity.

You can basically apply any algorithm that solves the Minimum Weight Hamiltonian Path Problem to the third part, these algorithms are usually equivalent to TSP algorithms (the only difference between these problems is that in the TSP you return to the source node after visiting all the other nodes).