greedy_tsp(G, weight='weight', source=None)
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.
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)$
The Graph should be a complete weighted undirected graph. The distance between all pairs of nodes should be included.
Edge data key corresponding to the edge weight. If any edge does not have this attribute the weight is set to 1.
Starting node. If None, defaults to next(iter(G))
If G is not complete, the algorithm raises an exception.
Returns the cycle (list of nodes) that a salesman can follow to minimize total weight of the trip.
Return a low cost cycle starting at :None:None:`source` and its cost.
>>> 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 31See :
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.approximation.traveling_salesman.greedy_tsp
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them