Ask Your Question
1

Traveling Salesman Problem

asked 2020-05-11 18:35:32 -0500

raefsjo gravatar image

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

Comments

Can you provide the graph?

slelievre gravatar imageslelievre ( 2020-05-12 16:30:46 -0500 )edit

1 answer

Sort by » oldest newest most voted
0

answered 2020-05-11 19:44:56 -0500

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

Comments

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 01:45:27 -0500 )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

Stats

Asked: 2020-05-11 18:35:32 -0500

Seen: 100 times

Last updated: May 11