Hash Dijkstra Algorithm for Approximate Minimal Spanning Tree

In order to overcome the low efficiency of Dijkstra (DK) algorithm in constructing Minimal Spanning Trees (MST) for large-scale datasets,this paper uses Locality Sensitive Hashing (LSH) to design a fast approximate algorithm,namely,LSHDK algorithm,to build MST in Euclidean space.The LSHDK algorithm can achieve a faster speed with small error by reducing computations in search of nearest points.Computational experiments show that it runs faster than the DK algorithm on datasets of more than 50 000 points,while the resulting approximate MST has an small error which is very small (0.00-0.05%) in low dimension,and generally between 0.1%-3.0% in high dimension.