Le problème de recherche k plus courts chemins base sur l'optimisation de l’algorithme SB

Abstract

Cette thèse présente une étude approfondie de la théorie des graphes, soulignant sa grande importance dans les applications du monde réel. La section d'introduction donne un aperçu de la théorie des graphes et de sa pertinence dans divers domaines, notamment les réseaux de transport et les connexions sociales. La théorie des graphes offre un cadre polyvalent pour comprendre les relations complexes et optimiser les systèmes en réseau. L'évolution historique du problème du chemin le plus court est ensuite explorée, retraçant son développement depuis les premières formulations jusqu'aux solutions algorithmiques contemporaines. Le problème “plus courts k simples chemins” est identifié comme une extension essentielle, avec des applications couvrant les transports, la communication et la biologie. L'objectif principal de cette thèse est l'algorithme Sidetrack Based (SB), une solution puissante au problème des k chemins simples les plus courts. Les principes, les forces et les limites de l'algorithme SB sont analysés, offrant une compréhension approfondie de son fonctionnement. De plus, les contributions originales de l'auteur visant à améliorer la praticité et l'efficacité de l'algorithme sont mises en évidence. Pour enrichir notre compréhension, des études comparatives des performances des algorithmes SB et PSB dans des réseaux distincts sont menées. L'analyse inclut la génération d'arbres et l'efficacité des calculs, mettant en lumière l'adaptabilité de l'algorithme à divers scénarios. Les réseaux étudiés vont des rues historiques de Rome au réseau complexe de la région de la baie de San Francisco. En conclusion, cette thèse sert de guide complet de l'algorithme SB et contribue à l'évolution continue des techniques d'optimisation de réseau au sein de la théorie des graphes. Il souligne le rôle essentiel de la théorie des graphes dans les applications modernes et montre comment des algorithmes innovants tels que SB peuvent remodeler notre capacité à analyser et optimiser des réseaux complexes. This thesis presents a thorough investigation of graph theory, emphasizing its broad significance in real world applications. The introductory section provides an overview of graph theory and its relevance in various domains, including transportation networks and social connections. Graph theory offers a versatile framework for comprehending complex relationships and optimizing networked systems. The historical evolution of the shortest path problem is then explored, tracing its development from early formulations to contemporary algorithmic solutions. The k Simple Shortest Paths Problem is identified as a pivotal extension, with applications spanning transportation, communication, and biology. The primary focus of this thesis is on the Sidetrack Based (SB) algorithm, a powerful solution to the k Simple Shortest Paths Problem. The SB algorithm's principles, strengths, and limitations are dissected, providing a deep understanding of its workings. Additionally, the author's original contributions aimed at enhancing the algorithm's practicality and efficiency are highlighted. To enrich our understanding, comparative studies of the SB and PSB algorithms’ performance in distinct networks are conducted. The analysis includes tree generation and computational efficiency, shedding

light on the algorithm's adaptability across diverse scenarios. The networks studied range from the historic streets of Rome to the intricate web of the San Francisco Bay Area. In conclusion, this thesis serves as a comprehensive guide to the SB algorithm and contributes to the ongoing evolution of network optimization techniques within graph theory. It underscores the critical role of graph theory in modern applications and showcases how innovative algorithms like SB can reshape our ability to analyze and optimize complex networks