Efektívne hľadanie viacerých najkratších ciest v orientovanom ohodnotenom grafe pomocou Dijkstrovho algoritmu v C# .NET aplikácii

Abstract

Dijkstra's algorithm is often used in various routing software, such as e.g. applications finding the shortest paths in the routing of packets by particular routers in computer networks represented by edge-weighted directed graphs. It can also be used to find the shortest paths in electronic road maps. We were interested in how to find efficiently several shortest paths in an edge-weighted directed graph using Dijkstra's algorithm. We have created a console C# .NET application that can use its instance method with implemented Dijkstra's algorithm to find several shortest paths in an edge-weighted directed graph in serial, on multiple threads and in parallel. In this paper, we deal with the execution efficiency of all three ways of finding and search for the most effective of them. We assume that the most efficient way to find several such shortest paths should be a parallel finding. The experiment we performed using our console C# .NET application will confirm or refute this hypothesis.