Algorithm: shortest path between all points

Question

Suppose I have 10 points. I know the distance between each point.

I need to find the shortest possible route passing through all points.

I have tried a couple of algorithms (Dijkstra, Floyd Warshall,...) and they all give me the shortest path between start and end, but they don't make a route with all points on it.

Permutations work fine, but they are too resource-expensive.

What algorithms can you advise me to look into for this problem? Or is there a documented way to do this with the above-mentioned algorithms?

Answer 1

Suppose I have 10 points. I know the distance between each point.

I need to find the shortest possible route passing through all points.

I have tried a couple of algorithms (Dijkstra, Floyd Warshall,...) and they all give me the shortest path between start and end, but they don't make a route with all points on it.

Permutations work fine, but they are too resource-expensive.

What algorithms can you advise me to look into for this problem? Or is there a documented way to do this with the above-mentioned algorithms?

Answer:

Try applying the Travelling Salesman Problem algorithm as it can resolve your query.

For example, consider the graph shown in the figure on the right side.

A TSP tour in the graph is 1-2-4-3-1.

The cost of the tour is 10+25+30+15 which is 80.

For n number of vertices or points in a graph, there are (n - 1)! the number of possibilities.

Here is a detailed algorithm about the working of TSP:

C ({1}, 1) = 0 // length between 1 and 1 is 0

for s = 2 to n do // s contains all the points

  for all subsets S Є {1, 2, 3, … , n} of size s and containing 1

     C (S, 1) = ∞ // length between s and 1 cannot be determined

  for all j Є S and j ≠ 1 // j should belong to s and it should not be at the first position

     C (S, j) = min {C (S – {j}, i) + d(i, j)// d(i,j) is the distance between i and j points

for i Є S and i ≠ j

}

Return minj C({1, 2, 3, …, n}, j) + d(j, i) // returns the shortest path

Watch this video to learn about Neural Networks:

Go through this Artificial Intelligence Course to get a clear understanding of Artificial Intelligence!