Ask Your Question

Traveling Salesman Problem

asked 2020-05-12 01:35:32 +0200

raefsjo gravatar image


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 flag offensive close merge delete



Can you provide the graph?

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

1 Answer

Sort by » oldest newest most voted

answered 2020-05-12 02:44:56 +0200

tmonteil gravatar image

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.

edit flag offensive delete link more


Thank you for answer me!

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?

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

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2020-05-12 01:35:32 +0200

Seen: 854 times

Last updated: May 12 '20