Shortest Path Problem with Obstacles: A Modified Dijkstra's Algorithm

Introduction The shortest path problem with obstacles requires dynamic adaptation of traditional graph algorithms to handle real-world constraints like blocked nodes/edges. While Dijkstra’s algorithm guarantees optimal paths in static graphs, its modified version addresses NP-hard obstacle constraints through iterative replanning and sensor integration, making it viable for robotics, autonomous vehicles, and disaster response systems   Historical Context 1956 : Dijkstra’s algorithm introduced for shortest paths in weighted graphs. 2022 : Improved Dijkstra variants emerged for mobile robots (MRs), integrating ultrasonic sensors for real-time obstacle detections. 2023 : The ETJ study introduced adjustable weight adaptation, enabling real-time updates to edge weights for obstacle avoidance[ETJ, 2023]. 2023 : Hybrid approaches like MEDWA combined vector fields with Dynamic Window Approach (DWA) for dense obstacle scenarios ...