Let V be a set of n points in the plane. The unit-disk graph G = (V, E) has vertex set V and an edge eᵤv in E between vertices u, v in V if the Euclidean distance between u and v is at most 1. The weight of each edge eᵤv is the Euclidean distance between u and v. Given V and a source point s in V we consider the problem of computing shortest paths in G from s to all other vertices. The previously best algorithm for this problem runs in O (n log2 n) time Wang and Xue, SoCG'19. The problem has an Omega (n log n) lower bound under the algebraic decision tree model. In this paper, we present an improved algorithm of O (n log2 n / log log n) time (under the standard real-RAM model). Furthermore, we show that the problem can be solved using O (n log n) comparisons under the algebraic decision tree model, matching the Omega (n log n) lower bound.
Brewer et al. (Thu,) studied this question.