Encontrar el camino más corto desde un vértice fuente hasta cualquier otro vértice en un grafo (camino más corto de una sola fuente, SSSP) se utiliza en una amplia gama de aplicaciones. Con la rápida expansión del volumen de datos de los grafos, estos son demasiado grandes para ser almacenados y procesados en una máquina independiente. Por lo tanto, realizar SSSP de forma distribuida en los clústeres de computadoras se convierte en una forma inevitable. Encontramos que el rendimiento de los algoritmos SSSP distribuidos existentes está limitado por el costo de comunicación entre los trabajadores, que es causado por la relajación global. Para eliminar el costoso costo de comunicación, proponemos un algoritmo SSSP distribuido eficiente LR-SSSP que reemplaza la relajación global con la relajación local. Además, proponemos dos optimizaciones, es decir, sincronización perezosa y relajación anticipada, para reducir la sincronización inválida y la comunicación. Nuestros resultados muestran que LR-SSSP puede lograr hasta 6-20 veces más velocidad que el algoritmo -stepping++ de última generación.