# Traveling Salesman Problem

Hello!

I'm a new user of SageMath, and I have a project that have 340 different places and I want to find a route to travel across the graph but, I don't want to travel trough the 340 places.

For example, if I want to find the TSP between just 5 points, I want to use de graph to find the shortest rout for just the 5 points I want passing trough the points it need, but no the 340, only the needed ones.

Anyone can help me with that?

edit retag close merge delete

Can you provide the graph?

( 2020-05-12 23:30:46 +0200 )edit

Sort by » oldest newest most voted

Here is a hint : if V denotes your set of 5 vertices., construct a graph whose vertices is V and for every par of vertices u and v of V, label the edge (u,v) with the length of the shortest path between u and v in the original graph (use the shortest_path method). What you want is a TSP in that reduced graph (use the traveling_salesman_problem method, with the option use_edge_labels=True.

more

I get what you said, and the only way I know to do that is by hand.

There's a way in which Sage made this automatically?

( 2020-05-12 08:45:27 +0200 )edit

## Stats

Seen: 199 times

Last updated: May 12 '20