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