helper.christofides_approx¶

helper.christofides_approx(G, source)[source]¶

Christofides’ Algorithm: 1.5-factor TSP approximation: Author: Juan Carlos Martinez Mori jm2638

Valid for metric traveling salesman problem.

Parameters:	G (graph) – The graph to apply algorithm to. source (node) – Node to be taken as root of MST.
Returns:	tour – Tour found by algorithm. [ source , nodes, source ].
Return type:	list