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

jgrapht.algorithms.tour.
metric_tsp_christofides
(graph)[source]¶ The Christofides 3/2approximation algorithm for the metric TSP.
For details see:
Christofides, N.: Worstcase 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

jgrapht.algorithms.tour.
metric_tsp_two_approx
(graph)[source]¶ A 2approximation algorithm for the metric TSP.
This is an implementation of the folklore algorithm which returns a depthfirst ordering of the minimum spanning tree. The algorithm is a 2approximation 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 2approximation
 Return type

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

jgrapht.algorithms.tour.
tsp_held_karp
(graph)[source]¶ A dynamic programming algorithm for the TSP.
Finds an optimal, minimumcost 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

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

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

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 twoopt 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

jgrapht.algorithms.tour.
tsp_two_opt_heuristic
(graph, k=1, min_cost_improvement=0.0001, seed=None)[source]¶ The 2opt heuristic algorithm for the TSP problem.
This is an implementation of the 2opt 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 2opt 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

jgrapht.algorithms.tour.
tsp_two_opt_heuristic_improve
(graph_path, min_cost_improvement=0.0001, seed=None)[source]¶ Improve a tour using the 2opt heuristic for the TSP problem.
This is an implementation of the 2opt 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 2opt 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.
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

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

abstract