A study on optimal path selection of some special graphs

Abstract

This thesis conducts a thorough investigation into the optimal path selection problem within a set of specialized graphs, namely Bi-Weighted Graphs, Bi-Weighted Bunch Graphs, Semidirected Graphs, Weighted Semidirected Graphs, and Random Graphs. These types of graphs have specific features that present special difficulties for determining the best and/or optimal paths, which makes them very important in a variety of applications like complex the modelling process, transportation systems, and network design. The research begins by providing a comprehensive review of existing literature on graph theory, shortest path algorithms, and the specific properties of each graph type. The study identifies and analyzes key factors influencing optimal path selection within these specialized structures, including the two weights in Bi-Weighted Graphs, the interconnected bunching in Bi-Weighted Bunch Graphs, the directed and undirected edges in Semidirected Graphs, the weighted directionality in Weighted Semidirected Graphs and probability distribution in Random Graphs. Novel algorithms and methodologies are proposed and developed to address the unique challenges posed by each graph type. The efficacy of these approaches is evaluated through computational experiments, considering factors such as computational complexity and solution optimality. Practical implications and applications of the optimal path selection in Bi-Weighted, Bi-Weighted Bunch, Semidirected, Weighted Semidirected, and Random Graphs are explored through real-world case studies. The results of these applications illustrate the significance of the proposed algorithms in newlineAbstract newlineXX newlineenhancing the efficiency of systems reliant on optimal pathfinding within specialized graph structures. The contributions of this research extend to both theoretical advancements in graph theory and the development of practical tools for optimization challenges within specialized graphs. Decision-makers and system designers can benefit from the insights gained, leading to improved pe