CODEWITHSUNDEEP
algorithmshortest-pathheuristicsminimum-spanning-tree
j4ckhunter
j4ckhunter

Reputation: 11

Algorithm: shortest travelling route between 10 cities

I have a graph with 80 cities. I need to find a shortest possible route passing through 10 cities.

I have to start from a city that already defined as starting city and user will enter 10 city names from the city list. I must travel this 10 cities and than I have to go back to the city where I started. I just have all the information about road distances between the cities that are adjacent.I haven't any information except that.

I know that Dijkstra, etc. found the shortest path between 2 cities and some heuristic algorithms need more data than that.

Can I use Dijkstra for the shortest path between starting city and other 10 cities and then find a min spanning tree of that and traverse on it? Is there any heuristic algorithm that I can use with this data?

Upvotes: 1

Views: 1963

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58221

Given your 10 cities, find the shortest path between each pair. That's only 45 calls to Dijkstra's algorithm. This gives you a complete graph on 10 vertices.

Now you have a travelling salesman problem, but 10 cities is not so many, and you're given the start city, so there's only 9! (362880) possibilities. I'd simply try all permutations and find the minimal one.

You can do something cleverer, but this simple brute-force solution will be fast and easy to code.

[edit: maybe you have a start city and 10 other cities. Still, 10! (3728800) is small enough to make searching every permutation fast enough]

Upvotes: 3

Related Questions