An Exhaustive Approach Orchestrating Negative Edges for Dijkstra’s Algorithm
- Resource Type
- Conference
- Authors
- Parekh, Sidharth; Jha, Abhishek; Dalvi, Ashwini; Siddavatam, Irfan
- Source
- 2022 IEEE 7th International conference for Convergence in Technology (I2CT) Convergence in Technology (I2CT), 2022 IEEE 7th International conference for. :1-5 Apr, 2022
- Subject
- Aerospace
Bioengineering
Communication, Networking and Broadcast Technologies
Components, Circuits, Devices and Systems
Computing and Processing
Engineered Materials, Dielectrics and Plasmas
Engineering Profession
Fields, Waves and Electromagnetics
General Topics for Engineers
Photonics and Electrooptics
Power, Energy and Industry Applications
Robotics and Control Systems
Signal Processing and Analysis
Transportation
Shortest path problem
Image edge detection
Conferences
Time complexity
Convergence
Dijkstra’s algorithm
Graph Theory
Negative edges
Modified Dijkstra’ algorithm
- Language
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.