Ask Your Question

# 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

## Comments

Can you provide the graph?

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

## 1 Answer

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

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

( 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

## Stats

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

Seen: 210 times

Last updated: May 12 '20