Is there a clustering algorithm that works with only pairwise distances as input?
Yes, this is a classic Graph-Based Clustering problem in which each location is a node and you have the distances between them. Forgetting about concept of graphs and graph-based algorithm which might be complicating, I directly jump to your answer.
The most well-known algorithm is Spectral Clustering. There are tones of tutorial out there and it is well implemented in all programming languages including Java.
I briefly explain but do not Panic if you are not familiar with Math terms. They are pretty intuitive and easy. You just need to follow a good tutorial.

Calculate the Similarity Matrix (often referred to as Affinity Matrix in literature). As you have distance matrix you have several ways to do it. Simplest starts from saying $sim = \frac{1}{dist}$ till more sophisticated ones which use Gaussian Kernels for calculating similarity.
Calculate the Laplacian Matrix out of similarity matrix.
Calculate eigenvectors and eigenvalues in order to embedd your data points into their eigen-space (like exactly what we do in PCA)
Use a simple clustering algorithm like K-Means to cluster points in that space