3

I'm looking for an algorithm that gives me the n nodes that are the farthest away from each other.

Can this be accomplished relatively efficiently?

To clarify my question: I think of the problem as a variant of the opposite of the travelling salesman problem. We have this graph:

graph

The distance matrix looks like this:

    a   b   c   d   e   f
a   0   184 222 177 216 231
b   184 0   45  123 128 200
c   222 45  0   129 121 203
d   177 123 129 0   46  83
e   216 128 121 46  0   83
f   231 200 203 83  83  0

For example, the salesman needs to visit any 4 nodes shown above. He must be on the road between all nodes he visits as long as possible. Which nodes would he visit?

My guess is we're looking for the 4 nodes with the maximum average distance between them. Is there a reasonably efficient, preferably non-exponential, way to do this? What if I don't need an exact solution to the problem?

  • 2
    Do you need the four largest distances, or the longest path? – HamHamJ Oct 3 '14 at 18:35
  • I'm looking for the four longest distances. – Sundae Oct 3 '14 at 22:24
  • This sounds to me somewhat like a TSP albeit in reverse, so probably no non-exponential solution. – 500 - Internal Server Error Oct 3 '14 at 23:17
  • Is the graph fully connected or sparse? This is a variant of the travelling salesman unless there are specific predetermined restrictions on the connectivity or distances. – David Scholefield Oct 6 '14 at 12:20
  • The graph is fully connected. – Sundae Oct 6 '14 at 18:07
1

To find the four longest distances, you need to search over all the distances. So for n nodes, you need to loop through n^2 distances, and so something like:

if dist > smallest_max
  replace smallest max in array of four maximums with dist
  recalculate the smallest max from array

This is O(n^2), which is not good but it's not exponential like traveling salesman.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.