How to find the minimum (or close to minimum) cost path that visits a subset of nodes within a graph? What algorithms can I use?

I googled and found: http://lcm.csa.iisc.ernet.in/dsa/node181.html

But the problem doesn't look like a minimum-cost spanning trees.

This is because the subset of nodes that I want to visit is not all of the nodes in a graph.

Sometimes there is no direct path between a node that I want to visit with any other nodes that I want to visit.

This means creating a subgraph that contains only the nodes I want to visit won't help because I definitely have to go through some of the nodes that I dont want to visit.

  • $\begingroup$ I guess... I could 1. Find the shortest path between any pairs of nodes that I want to visit. 2. Create a new graph between the nodes that I want, with edge that has cost representing the shortest path found in last step. 3. Find minimum-cost spanning tree. $\endgroup$ – hamster on wheels Aug 13 '17 at 20:45
  • $\begingroup$ Even if you subset of nodes includes all nodes, a spanning tree is not quite a path. However, you seem to apply that minimum spanning tree will solve your problem in the case in which your subset contains all nodes. Can you clarify that? $\endgroup$ – Yuval Filmus Aug 13 '17 at 21:10
  • $\begingroup$ I can't. You are right that a tree isn't a minimal path. I don't know what algorithm can work. Didn't take computer science class and just self studied. Worst case is to double every costs for going into a dead end and then walk back. $\endgroup$ – hamster on wheels Aug 13 '17 at 21:14
  • 1
    $\begingroup$ Does your problem turn in this case into Hamiltonian Path or TSP (Traveling Salesman Problem)? If so, it's NP-hard. $\endgroup$ – Yuval Filmus Aug 13 '17 at 21:22
  • 1
    $\begingroup$ It seems that your problem is equivalent to TSP, so you can look for algorithms for this classical problem. $\endgroup$ – Yuval Filmus Aug 13 '17 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.