New answers tagged weighted-graphs
1
Let $G=(V,E)$ be the graph and let $S$ be the set of cities you want to visit.
Since you talk about "covering" all the cities, it might be the case that you are fine with visiting cities more than once as long as all cities in $S$ are visited at least once. The problem is still NP-hard in this case (see Juho's answer), but it can be 1.5-...
1
The problem is NP-hard by a routine reduction, so you won't find an efficient algorithm unless P = NP. If the number of cities is not large, just try all orderings. Otherwise, you can resort to a heuristic (e.g., build the path city-by-city always picking say the one closest to your current location) or a more complex metaheuristic like a genetic algorithm.
Top 50 recent answers are included
