Single Source Shortest Path Algorithm - Based on Reverse Tracking from Destination, using Dynamic Programming
M Srihari, L Suresh, Bhagyashree Ambore, K. Sunitha · 2024
This research is conducted to design and develop a new algorithm for finding out the classic “Shortest Path” between every pair of vertices using an atypical approach. The approach follows the principle of optimality, and it is an enhanced version of traditional “Dijkstra’s and FloydWarshall” algorithms. Here, we begin with the “destination” node and backtrack to all the previous vertices. The core of the algorithm involves initializing data structures to track distances and paths, and then iteratively updating these values based on the shortest paths of the last visited vertices. By iteratively selecting the node with the minimum distance and considering its neighbours, the algorithm systematically constructs the shortest path. The result is a versatile and efficient technique for solving the shortest path problems for real-time applications. The algorithm’s adaptability and effectiveness make it a valuable addition to the toolkit of graph-related tasks, offering a unique perspective on finding the shortest path while accommodating applications in fields such as network routing, transportation, and logistics.