Coverage Path Planning (CPP) is crucial in robotics for tasks like environmental monitoring and search and rescue, demanding efficient area coverage while minimizing time and energy consumption. This paper presents a hybrid approach that integrates the exploration capabilities of the Random Walk algorithm with the optimal pathfinding of Dijkstra’s algorithm to enhance CPP efficiency. Our method addresses the limitations of traditional CPP techniques by enabling robots to navigate complex environments with obstacles while minimizing redundant movements. The integration of Dijkstra’s algorithm optimizes path segments between waypoints generated by the Random Algorithm, ensuring faster traversal times and reduced energy expenditure. This hybrid approach holds significant potential for enhancing the performance of robots in various applications requiring efficient and comprehensive area coverage. Simulation results confirm the effectiveness of our approach, revealing notable gains in coverage speed, workspace exploration, and pathfinding compared to standard Random Walk and Dijkstra’s algorithms.