Generalization of Dijkstra’s Algorithm for Extraction of Shortest Paths in Directed Multigraphs
- 1 Jamia Millia Islamia University, India
Abstract
The classical Dijkstra’s algorithm to find the shortest path in graphs is not applicable to multigraphs. In this study the authors generalize the classical Dijkstra’s algorithm to make it applicable to directed multigraphs. The modified algorithm is called by Generalized Dijkstra’s algorithm or GD Algorithm (GDA in short). The GDA outputs the shortest paths and the corresponding min cost. It is claimed that GDA may play a major role in many application areas of computer science, communication, transportation systems, in particular in those networks which cannot be modeled into graphs but into multigraphs.
DOI: https://doi.org/10.3844/jcssp.2013.377.382
Copyright: © 2013 Bashir Alam, Siddhartha Sankar Biswas and M. N. Doja. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 3,760 Views
- 11,584 Downloads
- 16 Citations
Download
Keywords
- Min-Weight Multiset
- Multigraphs
- Shortest Path Estimate
- Relaxation
- GDA