# Tour¶

## Algorithms¶

The travelling salesman problem (TSP) asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”.

The following algorithms are available:

jgrapht.algorithms.tour.hamiltonian_palmer(graph)[source]

Palmer’s algorithm for computing Hamiltonian cycles in graphs that meet Ore’s condition.

Running time $$\mathcal{O}(n^2)$$.

Parameters

graph – the input graph. Must be simple and meet Ore’s condition.

Returns

a hamiltonian cycle

Return type

GraphPath

jgrapht.algorithms.tour.metric_tsp_christofides(graph)[source]

The Christofides 3/2-approximation algorithm for the metric TSP.

For details see:

• Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Graduate School of Industrial Administration, Carnegie Mellon University (1976).

Running time $$\mathcal{O}(n^3 m)$$.

Parameters

graph – The input graph. Must be undirected, complete and satisfy the triangle inequality.

Returns

a tour which is a 3/2 approximation

Return type

GraphPath

jgrapht.algorithms.tour.metric_tsp_two_approx(graph)[source]

A 2-approximation algorithm for the metric TSP.

This is an implementation of the folklore algorithm which returns a depth-first ordering of the minimum spanning tree. The algorithm is a 2-approximation assuming that the instance satisfies the triangle inequality. The implementation requires the input graph to be undirected and complete. The running time is $$\mathcal{O}(n^2 \log n)$$.

Parameters

graph – the input graph. Must be undirected, complete and satisfy the triangle inequality

Returns

a tour which is a 2-approximation

Return type

GraphPath

jgrapht.algorithms.tour.tsp_greedy_heuristic(graph)[source]

Construct a tour greedily. The algorithm repeatedly selects the shortest edge and adds it to the tour as long as it doesn’t create a cycle with less than $$n$$ edges, or increases the degree of any node to more that two.

The runtime complexity is $$\mathcal{O}(n^2 \log n)$$.

Parameters

graph – the input graph. Must be undirected and complete

Returns

a greedy tour

Return type

GraphPath

jgrapht.algorithms.tour.tsp_held_karp(graph)[source]

A dynamic programming algorithm for the TSP.

Finds an optimal, minimum-cost Hamiltonian tour. Running time is $$\mathcal{O}(2^n \times n^2)$$ and space $$\mathcal{O}(2^n \times n)$$.

Parameters

graph – the input graph. Must be undirected and complete

Returns

an optimal tour

Return type

GraphPath

jgrapht.algorithms.tour.tsp_nearest_insertion_heuristic(graph)[source]

The nearest insertion heuristic algorithm for the TSP problem.

The runtime complexity is $$\mathcal{O}(n^2)$$.

Parameters

graph – the input graph. Must be undirected and complete

Returns

a tour

Return type

GraphPath

jgrapht.algorithms.tour.tsp_nearest_neighbor_heuristic(graph, seed=None)[source]

The nearest neighbour heuristic algorithm for the TSP problem.

The runtime complexity is $$\mathcal{O}(n^2)$$.

Parameters
• graph – the input graph. Must be undirected and complete

• seed – seed for the random number generator, use system time if None

Returns

a tour

Return type

GraphPath

jgrapht.algorithms.tour.tsp_random(graph, seed=None)[source]

Compute a random Hamiltonian cycle. This is a simple unoptimized solution to the Travelling Salesman Problem, suitable for a starting point in optimizing using the two-opt heuristic.

Parameters
• graph – the input graph. Must be undirected and complete

• seed – seed for the random number generator. If None then the seed is chosen based on the current time

Returns

A random tour

Return type

GraphPath

jgrapht.algorithms.tour.tsp_two_opt_heuristic(graph, k=1, min_cost_improvement=0.0001, seed=None)[source]

The 2-opt heuristic algorithm for the TSP problem.

This is an implementation of the 2-opt improvement heuristic algorithm. The algorithm generates k initial tours and then iteratively improves the tours until a local minimum is reached. In each iteration it applies the best possible 2-opt move which means to find the best pair of edges (i,i+1) and (j,j+1) such that replacing them with (i,j) and (i+1,j+1) minimizes the tour length. The default initial tours are constructed randomly.

Parameters
• graph – the input graph. Must be undirected and complete

• k – how many initial tours to generate

• min_cost_improvement – minimum cost improvement per iteration

• seed – seed for the random number generator, use system time if None

Returns

a tour

Return type

GraphPath

jgrapht.algorithms.tour.tsp_two_opt_heuristic_improve(graph_path, min_cost_improvement=0.0001, seed=None)[source]

Improve a tour using the 2-opt heuristic for the TSP problem.

This is an implementation of the 2-opt improvement heuristic algorithm. The algorithm takes as input a tour and then iteratively improves the tour until a local minimum is reached. In each iteration it applies the best possible 2-opt move which means to find the best pair of edges (i,i+1) and (j,j+1) such that replacing them with (i,j) and (i+1,j+1) minimizes the tour length.

Parameters
• graph – the input tour, instance of GraphPath

• min_cost_improvement – minimum cost improvement per iteration

• seed – seed for the random number generator, use system time if None

Returns

a tour

Return type

GraphPath

## Types¶

Tours are represented with instances of GraphPath.

class jgrapht.types.GraphPath[source]

Interface for a graph path.

abstract edges()[source]

Edges of the path.

Return type

collections.abc.Iterable

abstract end_vertex()[source]

Ending vertex of the path.

abstract graph()[source]

The graph that this graph path refers to.

Return type

jgrapht.types.Graph

abstract start_vertex()[source]

Starting vertex of the path.

property vertices

Vertices of the path.

abstract weight()[source]

Weight of the path.

Return type

Double