CODEWITHSUNDEEP
algorithmgraph-theoryshortest-path
Phil B
Phil B

Reputation: 6037

Algorithm to traverse k nodes of an undirected, weighted graph (and return to the origin) at the lowest cost

I am looking for an algorithm to do the following:

In an undirected, weighted graph with cycles

-find a path that visits exactly k nodes
-minimize the total cost(weight)
-each node can be visited only once
-return to the origin

edit: The start (and end) vertex is set in advance.

If I wanted to visit all nodes, the Traveling Salesman algorithm (and all its variations) would work. But in my case, the "salesman" needs to head home after visiting k nodes.

Both approximate and exact algorithms are fine in this case.

Upvotes: 1

Views: 184

Answers (1)

Marcus Ritt
Marcus Ritt

Reputation: 477

Since your problem includes the TSP for k=n as a special case in general it will be NP-complete. For small k you can adapt the dynamic programming solution of Bellmann (1962) to solve it in time O(2^k n^3).

Let T(u,S) be the length of the shortest route starting at vertex u with vertices in S visited already. Then you want the smallest of T(u0,{u0}) over all starting vertices u0. T satisfies the recurrence

T(u,S) = min { d(u,v)+T(v,S+{v}) | v in V\S }     if |S|<k
T(u,S) = d(u,u0)                                  if |S|=k

for distances d(u,v). The DP table has 2^kn entries, each entry takes O(n) time to compute, and you have to compute it n times, for each starting vertex.

Upvotes: 2

Related Questions