This paper proposes an optimal path planning algorithm incorporating a global and local search mechanism for mobile robots. The global path planning is based on Voronoi graph to establish a backbone path for the map with significantly reduced nodes for the original grid map. With the use of the backbone path, the D* algorithm is adopted to determine a shortest path between the starting and end points. Taking advantages of the D* algorithm and Voronoi graph, the proposed optimal path planning algorithm is capable of obtaining a desired path for the mobile robot, overcoming the efficiency problem while maintaining maximum safety distance from the obstacles when the mobile robot navigates in the environment. Simulation results have confirmed the feasibility of the proposed algorithm for practical use in the real-world environment.