Identifying the Shortest Path of a Semidirected Graph and Its Application

Rakhi Das, Laxminarayan Sahoo (), Sovan Samanta, Vladimir Simic and Tapan Senapati
Additional contact information
Rakhi Das: Department of Computer and Information Science, Raiganj University, Raiganj 733134, India
Laxminarayan Sahoo: Department of Computer and Information Science, Raiganj University, Raiganj 733134, India
Sovan Samanta: Department of Mathematics, Tamralipta Mahavidyalaya, Tamluk 721636, India
Vladimir Simic: Faculty of Transport and Traffic Engineering, University of Belgrade, Vojvode Stepe 305, 11010 Belgrade, Serbia
Tapan Senapati: Department of Mathematics, Padima Janakalyan Banipith, Jhargram 721517, India

Mathematics, 2022, vol. 10, issue 24, 1-13

Abstract: The basic goal of this research is to find the shortest path of a semidirected graph and apply it to the road network system. In the field of graph theory, networks are described as directed graphs, undirected graphs, or a combination of both. However, in the modern era of computing, several networks, such as social media networks, granular networks, and road transport networks, are not linked to any of the aforementioned network categories and in reality are a hybrid of networks with both directed and undirected interconnections. To better understand the notion of these types of networks, semidirected graphs have been developed to represent such networks. In a semidirect graph, both the directed and undirected edges concepts have been introduced together in a graph. In reality, it has been noted that for every node (source/destination) which is connected to another, some links/connections are directed—i.e., one-way—and some links/connections are undirected—i.e., two-way. Considering that there is no specific direction provided and that two nodes are connected, we have established the concept of an undirected edge as two-way connectivity since this provides for nodes in both ways. In this study, the road network system has been modelled using the concept of a semidirected graph, and the shortest path through it has been determined. For the purposes of illustration, we have used a real transportation road network in this case, and the computed results have been displayed.

Keywords: Semidirected graph; weighted graph; shortest path; mixed graph; road networks; Floyd–Warshall algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/24/4807/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/24/4807/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:24:p:4807-:d:1006537

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().