code: def traveling_salesman_problem(
      G, weight="weight", nodes=None, cycle=True, method=None
  ):
      """Find the shortest path in `G` connecting specified nodes
  
      This function allows approximate solution to the traveling salesman
      problem on networks that are not complete graphs and/or where the
      salesman does not need to visit all nodes.
  
      This function proceeds in two steps. First, it creates a complete
      graph using the all-pairs shortest_paths between nodes in `nodes`.
      Edge weights in the new graph are the lengths of the paths
      between each pair of nodes in the original graph.
      Second, an algorithm (default: `christofides` for undirected and
      `asadpour_atsp` for directed) is used to approximate the minimal Hamiltonian
      cycle on this new graph. The available algorithms are:
  
       - christofides
       - greedy_tsp
       - simulated_annealing_tsp
       - threshold_accepting_tsp
       - asadpour_atsp
  
      Once the Hamiltonian Cycle is found, this function post-processes to
      accommodate the structure of the original graph. If `cycle` is ``False``,
      the biggest weight edge is removed to make a Hamiltonian path.
      Then each edge on the new complete graph used for that analysis is
      replaced by the shortest_path between those nodes on the original graph.
      If the input graph `G` includes edges with weights that do not adhere to
      the triangle inequality, such as when `G` is not a complete graph (i.e
      length of non-existent edges is infinity), then the returned path may
      contain some repeating nodes (other than the starting node).
  
      Parameters
      ----------
      G : NetworkX graph
          A possibly weighted graph
  
      nodes : collection of nodes (default=G.nodes)
          collection (list, set, etc.) of nodes to visit
  
      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.
  
      cycle : bool (default: True)
          Indicates whether a cycle should be returned, or a path.
          Note: the cycle is the approximate minimal cycle.
          The path simply removes the biggest edge in that cycle.
  
      method : function (default: None)
          A function that returns a cycle on all nodes and approximates
          the solution to the traveling salesman problem on a complete
          graph. The returned cycle is then used to find a corresponding
          solution on `G`. `method` should be callable; take inputs
          `G`, and `weight`; and return a list of nodes along the cycle.
  
          Provided options include :func:`christofides`, :func:`greedy_tsp`,
          :func:`simulated_annealing_tsp` and :func:`threshold_accepting_tsp`.
  
          If `method is None`: use :func:`christofides` for undirected `G` and
          :func:`threshold_accepting_tsp` for directed `G`.
  
          To specify parameters for these provided functions, construct lambda
          functions that state the specific value. `method` must have 2 inputs.
          (See examples).
  
      Returns
      -------
      list
          List of nodes in `G` along a path with an approximation of the minimal
          path through `nodes`.
  
      Raises
      ------
      NetworkXError
          If `G` is a directed graph it has to be strongly connected or the
          complete version cannot be generated.
  
      Examples
      --------
      >>> tsp = nx.approximation.traveling_salesman_problem
      >>> G = nx.cycle_graph(9)
      >>> G[4][5]["weight"] = 5  # all other weights are 1
      >>> tsp(G, nodes=[3, 6])
      [3, 2, 1, 0, 8, 7, 6, 7, 8, 0, 1, 2, 3]
      >>> path = tsp(G, cycle=False)
      >>> path in ([4, 3, 2, 1, 0, 8, 7, 6, 5], [5, 6, 7, 8, 0, 1, 2, 3, 4])
      True
  
      Build (curry) your own function to provide parameter values to the methods.
  
      >>> SA_tsp = nx.approximation.simulated_annealing_tsp
      >>> method = lambda G, wt: SA_tsp(G, "greedy", weight=wt, temp=500)
      >>> path = tsp(G, cycle=False, method=method)
      >>> path in ([4, 3, 2, 1, 0, 8, 7, 6, 5], [5, 6, 7, 8, 0, 1, 2, 3, 4])
      True
  
      """
      if method is None:
          if G.is_directed():
              method = asadpour_atsp
          else:
              method = christofides
      if nodes is None:
          nodes = list(G.nodes)
  
      dist = {}
      path = {}
      for n, (d, p) in nx.all_pairs_dijkstra(G, weight=weight):
          dist[n] = d
          path[n] = p
  
      if G.is_directed():
          # If the graph is not strongly connected, raise an exception
          if not nx.is_strongly_connected(G):
              raise nx.NetworkXError("G is not strongly connected")
          GG = nx.DiGraph()
      else:
          GG = nx.Graph()
      for u in nodes:
          for v in nodes:
              if u == v:
                  continue
              GG.add_edge(u, v, weight=dist[u][v])
      best_GG = method(GG, weight)
  
      if not cycle:
          # find and remove the biggest edge
          (u, v) = max(
              pairwise(best_GG), key=lambda x: dist[x[0]][x[1]]
          )
          pos = best_GG.index(u) + 1
          while best_GG[pos] != v:
              pos = best_GG[pos:].index(u) + 1
          best_GG = best_GG[pos:-1] + best_GG[:pos]
  
      best_path = []
      for u, v in pairwise(best_GG):
          best_path.extend(path[u][v][:-1])
      best_path.append(v)
      return best_path
  
file_path: networkx/networkx/algorithms/approximation/traveling_salesman.py
imports: import math
  import networkx
  from networkx.algorithms.tree.mst import random_spanning_tree
  from networkx.utils import not_implemented_for, pairwise, py_random_state
label_desc: Use image node_id 5 for calling a global function with example usage: traveling_salesman_problem(G, weight, nodes, cycle, method) and returns: best_path