An Exhaustive Approach Orchestrating Negative Edges for Dijkstra’s Algorithm

The single source shortest path is a problem which consists of finding shortest path between a particular node and all the other nodes present in the graph. The Dijkstra’s algorithm is used to solve the single-source shortest path problem. The limitation with Dijkstra’s algorithm is it does not consider negative edges and may or may not give befitting results in every scenario. In this paper, we propose an exhaustive approach that provides an extension to Dijkstra’s algorithm to detect all those nodes whose calculated shortest path by it gets competed with smaller value of another route having negative edges. Experiments have been carried out to compare the results of solution proposed with Dijkstra and Bellman Ford algorithms to prove its potency.