# Find n nodes farthest away from each other

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:

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?

• Do you need the four largest distances, or the longest path? Oct 3, 2014 at 18:35
• I'm looking for the four longest distances. Oct 3, 2014 at 22:24
• This sounds to me somewhat like a TSP albeit in reverse, so probably no non-exponential solution. Oct 3, 2014 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. Oct 6, 2014 at 12:20
• The graph is fully connected. Oct 6, 2014 at 18:07

``````if dist > smallest_max