Optimal Path Selection for a Weighted Semidirected Network and its Application

Abstract

Abstract This paper deals with optimal path selection within the context of weighted semidirected graphs, which combine both directed and undirected edges. In real life, it is seen that road networks are sometimes laid out in a unidirectional manner. Sometimes, it is also seen as a combination of unidirectional, bidirectional, or semidirected road structures. In a semidirected path, vehicles traverse both sides, resulting in congestion. Due to congestion, the travel time increased comparatively for semidirected paths relative to undirected paths. The study aims to develop efficient algorithms for identifying the most advantageous routes in scenarios where edges possess varying weights, reflecting diverse costs or distances between nodes. The chapter begins by introducing weighted semidirected graphs, establishing the shortest-path/optimal-path algorithm, and discussing its significance in real-world applications. The proposed algorithm is developed to evaluate the congestion of a semidirected graph, considering both the directionality and weights associated with each edge. The research emphasizes developing optimal path algorithms that enhance computational efficiency while identifying paths that minimize specific criteria, such as total weight, traversal time, or resource utilization. A real-world case study involving transport networks illustrates how the suggested algorithm can be applied in practice. This exploration contributes valuable knowledge to graph theory, operations research, and computer science, offering a sophisticated way to address complex routing challenges in dynamic and interconnected systems.