The challenge of finding the shortest path in graphs containing cycles and negative weights presents substantial difficulties across multiple fields, including transportation, social network analysis, and the study of complex systems. While sequential algorithms provide effective solutions for small to medium-sized graphs, they become impractical for large graphs due to constraints in processing time and computational resources. This paper presents an extension of the shortest path algorithm into a parallel computing environment, leveraging the power of modern multicore systems. Experimental results demonstrate that the parallel version achieves superior performance compared to traditional algorithms, making it suitable for handling large-scale graphs efficiently.