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?

  • 2
    Do you need the four largest distances, or the longest path?
    – HamHamJ
    Oct 3, 2014 at 18:35
  • I'm looking for the four longest distances.
    – Sundae
    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.
    – Sundae
    Oct 6, 2014 at 18:07

1 Answer 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 and acknowledge you have read our privacy policy.

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