CODEWITHSUNDEEP
algorithmgraphtraveling-salesman
Samuel Benitah
Samuel Benitah

Reputation: 11

Traveling salesman on a directed graph with extra nods

I've been reading about different algorightms for solving the traveling salesman problem but can`t seem to find a example where you do not wish to visit all the nods in the graph. In example, lets say I have a graph made up of the nods n1,n2,n3,n4,n5,n6. In the classic traveling salesman problem I would want to visit all the nods in the shortest time possible. But what if I wish to leave from n1 and visit n3 n5 and n6 only. I can pass through the other nods if I have to but the only ones I absolutely have to visit are n1 n3 n5 n6 and back to n1. This means that what I'm looking for is the shortest path from n1 to n1 that passes through these 3 points. Any hint on which algorithm to look at would be welcome.

Thank you

Samuel Benitah

Upvotes: 1

Views: 1489

Answers (1)

Pradhan
Pradhan

Reputation: 16737

Let V be the set of vertices the you are required to visit. Let d(u,v) be the length of the shortest path from u to v. For every pair of vertices u and v in V, add an edge from u to v with length d(u,v). Let this graph be G, i.e., G is the original graph augmented by these edges. Let G_V be the G restricted to V. Your problem is equivalent to solving the TSP on G_V. To see this, note that if P is a segment in an optimal path in G satisfying your constraints such that only its endpoints(say u and v) lie in V, then the length of P should be d(u,v). If not, you can replace that segment by a shortest path from u to v and improve the optimal solution.

Upvotes: 1

Related Questions