We consider a non-directed graph, where each vertex is a city and each edge is a possible road connecting two cities.
I need to build a cheap highway (a path on a graph) connecting all the cities starting and ending with the main city. I know the cost to build each edge that connects two verteces (connects two cities). This is the only restriction: to visit all vertices of the graph. The goal is to minimize the cost to build this highway.
This problem is similar to the Traveling salesman problem, but here I can visit each vertex of the graph more than once, and also only the first time that I use an edge I pay to build it, but from the second it has no cost.
I'm not sure if I can connect the Traveling salesman problem with my problem, may be there are other way to solve it. I appreciate a lot your help.
This is the minimum spanning tree problem, and a greedy algorithm is optimal.