{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n# Traveling Salesman Problem\n\nThis is an example of a drawing solution of the traveling salesman problem\n\nThe function used to produce the solution is `christofides <networkx.algorithms.approximation.traveling_salesman.christofides>`,\nwhere given a set of nodes, it calculates the route of the nodes\nthat the traveler has to follow in order to minimize the total cost.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\nimport networkx as nx\nimport networkx.algorithms.approximation as nx_app\nimport math\n\nG = nx.random_geometric_graph(20, radius=0.4, seed=3)\npos = nx.get_node_attributes(G, \"pos\")\n\n# Depot should be at (0,0)\npos[0] = (0.5, 0.5)\n\nH = G.copy()\n\n\n# Calculating the distances between the nodes as edge's weight.\nfor i in range(len(pos)):\n for j in range(i + 1, len(pos)):\n dist = math.hypot(pos[i][0] - pos[j][0], pos[i][1] - pos[j][1])\n dist = dist\n G.add_edge(i, j, weight=dist)\n\ncycle = nx_app.christofides(G, weight=\"weight\")\nedge_list = list(nx.utils.pairwise(cycle))\n\n# Draw closest edges on each node only\nnx.draw_networkx_edges(H, pos, edge_color=\"blue\", width=0.5)\n\n# Draw the route\nnx.draw_networkx(\n G,\n pos,\n with_labels=True,\n edgelist=edge_list,\n edge_color=\"red\",\n node_size=200,\n width=3,\n)\n\nprint(\"The route of the traveller is:\", cycle)\nplt.show()"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.7"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Generated by dwww version 1.16 on Wed Apr 8 10:57:28 CEST 2026.