Efficiently finding the shortest path in a graph is a fundamental problem with diverse applications across numerous domains, from transportation and network routing to social network analysis and bioinformatics. This paper presents a comprehensive approach to improving the efficiency of shortest path searches in generic graphs. The contributions encompass novel algorithmic enhancements and parallelization techniques to tackle this critical problem. These algorithmic enhancements optimize the traversal of graphs with diverse data types and leverage data encodings to enhance search speed, thus reducing computational overhead and making it feasible to handle large-scale graphs efficiently. To further expedite the shortest path search process, the parallelization technique harnesses the power of modern multi-core processors and distributed computing environments. By efficiently distributing the workload among multiple processing units, this strategy significantly accelerates the state-of-the-art algorithms like Dijkstra’s, to explore candidate paths, leading to substantial improvements in query response times. This approach has demonstrated superior performance characteristics in various scenarios and provides an additional layer of optimization. Evaluation of the parallelized approach on benchmark graph datasets has showcased its effectiveness by improving search efficiency and scalability over existing methods like Dijkstra’s Algorithm, A* Heuristic Search and the Bellman-Ford Algorithm. By integrating algorithmic enhancements and parallelization, the novel approach opens up new avenues for solving complex shortest path problems more efficiently with limited computational resources. This paper not only contributes to the field of graph algorithms but also provides a valuable toolkit for practitioners seeking to optimize shortest path searches in graph-based data structures.