I consistently get shorter paths when the weight parameter is named weight
:
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))
# 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")
or with cycle=True
:
So it looks a bit like a bug to me at the moment.