Repository: networkx/networkx
Issue category: Bug Report

Issue:
traveling_salesman_problem seems to ignore the weight parameter
### Current Behavior

`traveling_salesman_problem` returns long paths when `weight` is named something other than 'weight'.

### Expected Behavior

`traveling_salesman_problem` should use the `weight` param to allow the correct edge attribute to be selected.

### Steps to Reproduce

```
import shapely
import networkx as nx
import matplotlib.pyplot as plt

# Make a 10x10 grid

vert = shapely.geometry.MultiLineString([[(x, 0), (x, 100)] for x in range(0, 110, 10)])
hori = shapely.affinity.rotate(vert, 90)
grid = shapely.unary_union([vert, hori])

params = ["weight", "distance"]
paths = []

for param in params:

    # Turn it into a graph

    graph = nx.Graph()
    graph.add_edges_from([(*line.coords, {param: line.length}) for line in grid.geoms])
    
    # Select nodes and visit them via TSP
    
    nodes = [(20., 20.), (30., 30.), (20., 80.), (80., 20.), (50., 50.), (60., 10.), (40., 40.), (50., 40.), (50, 30)]
    
    path = nx.approximation.traveling_salesman_problem(
        graph,
        weight=param,
        nodes=nodes,
        cycle=False,
        method=nx.approximation.christofides
    )
    
    paths.append(shapely.geometry.LineString(path))

print([path.length for path in paths])

```

> [240.0, 340.0]

### Environment

<!--- Please provide details about your local environment -->

Python version: 3.11 & 3.10.12
NetworkX version: 3.2.1 & 3.4.2

### Additional context
```
# Plot results

fig, axes = plt.subplots(1, 2, figsize=(10, 5), sharey=True)

for ax, param, path, c in zip(axes, params, paths, ["b", "r"]):
    for line in grid.geoms:
        ax.plot(*line.xy, c="k", lw=.25)
    ax.scatter(*zip(*nodes), c="k")
    ax.plot(*path.xy, c=c)
    ax.set_title(f"Param={param}, length={path.length}")
    ax.set_aspect("equal")
```
![image](https://github.com/user-attachments/assets/ef5dd219-997a-416f-b934-75ca1e5a5516)



Hints:
Thanks for the issue, there is indeed a bug here!

Specifically, in the graph pre-processing for `traveling_salesman_problem`, we rebuild the graph to restrict it to the nodes passed in via the `nodes` parameter, create a complete graph and re-weight the graph to ensure it satisfies the triangle inequality (which is a requirement for algorithms like `christofides`). During this process we see 

```python 
GG.add_edge(u, v, weight=dist[u][v])
```

which will replace the name of the attribute storing the weight with `"weight"`, and then pass the user-supplied `weight` value to the method. 

Fortunately this is an easy fix, we just need to change this line to 

```python
GG.add_edge(u, v, **{weight: dist[u][v]})
```

to preserve the user-supplied weight attribute name. 

Patch:
diff --git a/networkx/algorithms/approximation/traveling_salesman.py b/networkx/algorithms/approximation/traveling_salesman.py
index 2080c99aec7..f2c37d9cc40 100644
--- a/networkx/algorithms/approximation/traveling_salesman.py
+++ b/networkx/algorithms/approximation/traveling_salesman.py
@@ -334,7 +334,9 @@ def traveling_salesman_problem(
         for v in nodes:
             if u == v:
                 continue
-            GG.add_edge(u, v, weight=dist[u][v])
+            # Ensure that the weight attribute on GG has the
+            # same name as the input graph
+            GG.add_edge(u, v, **{weight: dist[u][v]})
 
     best_GG = method(GG, weight=weight, **kwargs)
 


Test patch:
diff --git a/networkx/algorithms/approximation/tests/test_traveling_salesman.py b/networkx/algorithms/approximation/tests/test_traveling_salesman.py
index 28791daac7d..bb309fc705d 100644
--- a/networkx/algorithms/approximation/tests/test_traveling_salesman.py
+++ b/networkx/algorithms/approximation/tests/test_traveling_salesman.py
@@ -394,6 +394,34 @@ def test_TSP_incomplete_graph_short_path():
     assert len(path) == 13 and len(set(path)) == 12
 
 
+def test_TSP_alternate_weight():
+    G = nx.complete_graph(9)
+    G[0][1]["weight"] = 2
+    G[1][2]["weight"] = 2
+    G[2][3]["weight"] = 2
+    G[3][4]["weight"] = 4
+    G[4][5]["weight"] = 5
+    G[5][6]["weight"] = 4
+    G[6][7]["weight"] = 2
+    G[7][8]["weight"] = 2
+    G[8][0]["weight"] = 2
+
+    H = nx.complete_graph(9)
+    H[0][1]["distance"] = 2
+    H[1][2]["distance"] = 2
+    H[2][3]["distance"] = 2
+    H[3][4]["distance"] = 4
+    H[4][5]["distance"] = 5
+    H[5][6]["distance"] = 4
+    H[6][7]["distance"] = 2
+    H[7][8]["distance"] = 2
+    H[8][0]["distance"] = 2
+
+    assert nx_app.traveling_salesman_problem(
+        G, weight="weight"
+    ) == nx_app.traveling_salesman_problem(H, weight="distance")
+
+
 def test_held_karp_ascent():
     """
     Test the Held-Karp relaxation with the ascent method