Skip to main content
`Ctrl`+`K`

# 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:
    G Graph

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

    weight string, 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.

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

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

  Returns:
    cycle list 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