Research Article Open Access

Generalization of Dijkstra’s Algorithm for Extraction of Shortest Paths in Directed Multigraphs

Siddhartha Sankar Biswas1, Bashir Alam1 and M. N. Doja1
  • 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.

Journal of Computer Science
Volume 9 No. 3, 2013, 377-382

DOI: https://doi.org/10.3844/jcssp.2013.377.382

Submitted On: 1 February 2013 Published On: 29 April 2013

How to Cite: Biswas, S. S., Alam, B. & Doja, M. N. (2013). Generalization of Dijkstra’s Algorithm for Extraction of Shortest Paths in Directed Multigraphs. Journal of Computer Science, 9(3), 377-382. https://doi.org/10.3844/jcssp.2013.377.382

  • 2,911 Views
  • 10,967 Downloads
  • 15 Citations

Download

Keywords

  • Min-Weight Multiset
  • Multigraphs
  • Shortest Path Estimate
  • Relaxation
  • GDA