Ask Your Question
1

Traveling Salesman Problem

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

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

1

Can you provide the graph?

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

1 Answer

Sort by » oldest newest most voted
1

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

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 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

Stats

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

Seen: 854 times

Last updated: May 12 '20