Finding path between all points using approximation algorithm

2
votes

There is 1<=n<=1000 cities. I have to find path that connects all the cities (every city can be visited only once) which starts and ends in city number 1. In this path the maximum length between 2 cities must be as short as possible.

Eg:

enter image description here

Input:

coordinates of cities

Output:

5 1 3 //longest connection is 5 and it is between cities 1 and 3
1 3 6 4 5 2 1 //path
2
algorithmpathcoordinatesapproximation
@phant0m, this is incorrect, as limitations different, "Max length" and "total sum". - Толя
Do you need a approximate algorithm? If so, you should add that to the question, and not just the title. I realized you needed an approximate algorithm from your tags, not the title. - Paresh

2 Answers

2
votes

Here is an approximation algorithm that should give better results on average than a naive greedy algorithm:

  1. Consider the graph to be complete - there is an edge between every pair of vertices for a total of n(n-1)/2 edges.
  2. Sort the edges in descending order of their weights/distances.
  3. Iterate from the highest distance edge to the lowest distance edge, and remove it if after removing that edge, both its end-points still have degree atleast ceil(n/2) (Dirac's theorem for ensuring a Hamiltonian cycle exists). You could use a stronger result like Ore's theorem to be able to trim even more edges, but the computation complexity will increase.
  4. In the remaining graph, use a greedy algorithm to find a Hamiltonian cycle. The greedy algorithm basically starts from 1, and keeps selecting the edge with the least distance to a node that does not already form part of the cycle so far. So in your example, it will first pick 1 -> 2, then 2->4, then 4->5 and so on. The last selected vertex will then have a path back to 1.

You could directly use the greedy algorithm given in step 4 on the input graph, but the pre-processing steps 1-3 should in general greatly improve your results on most graphs.

0
votes

Sounds similar to TSP except that you need to minimize the max length between 2 cities rather than the total (which probably makes it fundamentally different).

My thought is something like:

create edges between each pair of cities
while (true)
  next = nextLongestEdge
  if (graph.canRemove(next)) // this function may be somewhat complicated,
                             // note that it must at the very least check that every node has at least 2 edges
    graph.remove(next)
  else
    return any path starting and ending at 1 from the remaining edges