CODEWITHSUNDEEP
algorithmdijkstrashortest-path
Matej
Matej

Reputation: 13

shortest path from multiple Sets

I have to find the shortest path beetween nodes in various sets, where I can use node only once from every set. Every node is connected via distance to every others nodes. There is exception where nodes in set are not connected between them. The path must contain one node from every set.

eg. 

    Set A - [a1, a2, a3]
    Set B - [b1, b2]
    Set C - [c1]
    Set D - [d1, d2, d3]
    Set Z - [z1, z2, z3]

The nodes are a1,a2,a3,b1,b2...

eg. The node a1 have connection with

b1,b2,c1,d1,d2,d3,z1,z2,z3

or node c1 have connection with

a1,a2,a3,b1,b2,d1,d2,d3,z1,z2,z3

The posibble path could be :

a1 -> b1 -> c1 -> d1 -> z1, or c1 -> z2 -> a3 -> b1 -> d2

The distance between every nodes (except nodes in set, there is no connection ) could be from 0 to 1.

Upvotes: 1

Views: 357

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

This is known as the Generalised Travelling Salesman Problem.

From C. Noon & J.Bean, An Efficient Transformation of the Generalized Traveling Salesman Problem:

The Generalized Traveling Salesman Problem (GTSP) is a useful model for problems involving decisions of selection and sequence. The asymmetric version of the problem is defined on a directed graph with nodes N, connecting arcs A and a vector of corresponding arc costs c. The nodes are pregrouped into m mutually exclusive and exhaustive nodesets. Connecting arcs are defined only between nodes belonging to different sets, that is, there are no intraset arcs. Each defined arc has a corresponding non-negative cost. The GTSP can be stated as the problem of finding a minimum cost m-arc cycle which includes exactly one node from each nodeset.

This paper explains how to transform your problem to a case of the standard Travelling Salesman Problem.

Upvotes: 1

Related Questions