# Algorithm to find a low cost path that visits specific nodes in a graph

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?

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.

• 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. – hamster on wheels Aug 13 '17 at 20:45
• 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? – Yuval Filmus Aug 13 '17 at 21:10
• 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. – hamster on wheels Aug 13 '17 at 21:14
• Does your problem turn in this case into Hamiltonian Path or TSP (Traveling Salesman Problem)? If so, it's NP-hard. – Yuval Filmus Aug 13 '17 at 21:22
• It seems that your problem is equivalent to TSP, so you can look for algorithms for this classical problem. – Yuval Filmus Aug 13 '17 at 21:30