Identifying the Shortest Path of a Semidirected Graph and Its Application

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