Traveling Salesman Problem

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

raefsjo
11 ●1 ●1 ●2

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?

Comments

Can you provide the graph?

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

add a comment

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

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

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

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 ( 2020-05-12 08:45:27 +0100 )edit

add a comment

Your Answer

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

Traveling Salesman Problem

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Traveling Salesman Problem edit

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Traveling Salesman Problem