CODEWITHSUNDEEP
algorithmgraphshortest-pathdijkstratraveling-salesman
Paul
Paul

Reputation: 53

Traveling Saleperson Variation, Plotting a travel itinery

Im looking for the name of a problem and an algortihm for its solution.

I have a graph of connected nodes (A..Z) where every node is connected to every other node. I would like to plot the shortest path through these nodes that visits a given subset of nodes (A,D,K,W). The path may include nodes not in the subset ie A->C->W->D->K is acceptable. The cost of traveling between nodes is non negative, but not necessarily linear. Thus a path segment from A->B->C may be 'shorter' than A->C

I assume it is a variation of Traveling salesperson.

Upvotes: 2

Views: 159

Answers (1)

Qnan
Qnan

Reputation: 3744

I don't know if there is a special name for this problem, but it is easily reduced to the original traveling salesman problem for the selected nodes.

Let the set of all nodes be V and the selected ones W. I would start by collapsing the nodes not in the W to get a multigraph (like a graph, but can have multiple edges between the same pair of nodes). Each edge here may be a simple one or a sequence of edges and nodes from V\W. To reduce it to a regular graph, we have only to pick the shortest of the edges available for each pair of nodes, since any other would clearly not be a part of the answer. Now we have to solve the resulting traveling salesman problem for the reduced graph and then reconstruct the corresponding path in the original graph -- we have written down the actual path in the original graph each edge in the reduced graph corresponds to.

Upvotes: 2

Related Questions