greedy_tsp#

greedy_tsp(G, weight='weight', source=None)[source]#

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
On this page