dwave.graphs.algorithms.tsp.traveling_salesperson#

traveling_salesperson(graph: Graph, sampler: Sampler, lagrange: float | None = None, weight: str = 'weight', start: Hashable | None = None, **sampler_args) → Sequence[Hashable][source]#

Returns an approximate minimum traveling salesperson route.

Defines a binary quadratic model (BQM) with ground states corresponding to the minimum routes and uses the sampler to sample from it.

A route is a cycle in the graph that reaches each node exactly once. A minimum route is a route with the smallest total edge weight.

Parameters:

  • graph – The graph on which to find a minimum traveling salesperson route. This should be a complete graph with non-zero weights on every edge.

  • sampler – A dimod sampler.

  • lagrange – Lagrange parameter to weight constraints (visit every city once) versus objective (shortest distance route). If not specified, it’s estimated based on graph size. See traveling_salesperson() BQM generator.

  • weight – The name of the edge attribute containing the weight.

  • start – If provided, the route will begin at start.

  • **sampler_args – Additional keyword parameters passed to the sampler.

Returns:

List of nodes in order to be visited on a route.

Example

>>> import dimod
>>> import dwave.graphs
>>> import networkx
...
>>> G = networkx.Graph()
>>> G.add_weighted_edges_from({(0, 1, .1), (0, 2, .5), (0, 3, .1),
...                            (1, 2, .1), (1, 3, .5), (2, 3, .1)})
>>> dwave.graphs.traveling_salesperson(G, dimod.ExactSolver(), start=0)
[0, 1, 2, 3]