greedy_tsp

greedy_tsp(G, weight='weight', source=None)

Return a low cost cycle starting at source and its cost.

This approximates a solution to the traveling salesman problem. It finds a cycle of all the nodes that a salesman can visit in order to visit many nodes while minimizing total distance. It uses a simple greedy algorithm. In essence, this function returns a large cycle given a source point for which the total cost of the cycle is minimized.

Parameters

GGraph

The Graph should be a complete weighted undirected graph. The distance between all pairs of nodes should be included.

weightstring, optional (default=”weight”)

Edge data key corresponding to the edge weight. If any edge does not have this attribute the weight is set to 1.

sourcenode, optional (default: first node in list(G))

Starting node. If None, defaults to next(iter(G))

Returns

cyclelist of nodes

Returns the cycle (list of nodes) that a salesman can follow to minimize total weight of the trip.

Raises

NetworkXError

If G is not complete, the algorithm raises an exception.

Notes

This implementation of a greedy algorithm is based on the following:

• The algorithm adds a node to the solution at every iteration.

• The algorithm selects a node not already in the cycle whose connection to the previous node adds the least cost to the cycle.

A greedy algorithm does not always give the best solution. However, it can construct a first feasible solution which can be passed as a parameter to an iterative improvement algorithm such as Simulated Annealing, or Threshold Accepting.

Time complexity: It has a running time \(O(|V|^2)\)

Examples

>>> from networkx.algorithms import approximation as approx
>>> G = nx.DiGraph()
>>> G.add_weighted_edges_from({
...     ("A", "B", 3), ("A", "C", 17), ("A", "D", 14), ("B", "A", 3),
...     ("B", "C", 12), ("B", "D", 16), ("C", "A", 13),("C", "B", 12),
...     ("C", "D", 4), ("D", "A", 14), ("D", "B", 15), ("D", "C", 2)
... })
>>> cycle = approx.greedy_tsp(G, source="D")
>>> cost = sum(G[n][nbr]["weight"] for n, nbr in nx.utils.pairwise(cycle))
>>> cycle
['D', 'C', 'B', 'A', 'D']
>>> cost
31