Efektívne hľadanie viacerých najkratších ciest v orientovanom ohodnotenom grafe pomocou Dijkstrovho algoritmu v C# .NET aplikácii
Klíčová slova:
orientovaný ohodnotený graf, najkratšie cesty v grafe, prioritná fronta, Dijkstrov algoritmus, viacvláknové vyhľadávanie, paralelné vyhľadávanieAbstrakt
Dijkstrov algoritmus je často používaný v rôznych smerovacích softvéroch, ako sú napr. aplikácie hľadajúce najkratšie cesty pri smerovaní paketov jednotlivými smerovačmi v počítačových sieťach reprezentovaných orientovanými ohodnotenými grafmi. Tiež je ho možné použiť pre hľadanie najkratších ciest v elektronických automapách. Zaujímalo nás, ako sa dajú efektívne vyhľadávať viaceré najkratšie cesty v orientovanom ohodnotenom grafe pomocou Dijkstrov algoritmu. Vytvorili sme konzolovú C# .NET aplikáciu, ktorá dokáže pomocou svojej inštančnej metódy s implementovaným Dijkstrovým algoritmom vyhľadávať viaceré najkratšie cesty v orientovanom ohodnotenom grafe sériovo, na viacerých vláknach a paralelne. V článku sa zaoberáme exekučnou efektívnosťou všetkých troch spôsobov vyhľadávania a hľadáme najefektívnejší z nich. Predpokladáme, že najefektívnejším spôsobom vyhľadávania viacerých takýchto najkratších ciest by malo byť paralelné vyhľadávanie. Experiment, ktorý sme vykonali pomocou našej konzolovej C# .NET aplikácie, túto hypotézu potvrdí alebo vyvráti.Reference
[1] Košťál, I. (2020). Vplyv dátovej štruktúry použitej pre ukladanie dát grafu na exekučnú efektívnosť metód hľadajúcich v ňom najkratšie cesty pomocou Dijkstrovho algoritmu. AIESA 2020 medzinárodná vedecká konferencia. AIESA - Budovanie spoločnosti založenej na vedomostiach. Bratislava: Letra Edu.
[2] Niemann, T. (1999). Sorting and Searching Algorithms. epaperpress.com.
[3] Oumghar, K. (2015, December 22). Graphs and Dijkstra’s Algorithm (C#). Retrieved August 30, 2020, from
https://simpledevcode.wordpress.com/2015/12/22/graphs-and-dijkstras-algorithm-c/.
[4] Sedgewick, R. (1998). Algorithms in C parts 1-4. Fundamentals, data structures, sorting, searching. Addison-Wesley Publishing Company, Inc.
[5] Sedgewick, R. (2018). Algorithms, 4th Edition. Retrieved January 12, 2021, from
https://algs4.cs.princeton.edu/home/
[2] Niemann, T. (1999). Sorting and Searching Algorithms. epaperpress.com.
[3] Oumghar, K. (2015, December 22). Graphs and Dijkstra’s Algorithm (C#). Retrieved August 30, 2020, from
https://simpledevcode.wordpress.com/2015/12/22/graphs-and-dijkstras-algorithm-c/.
[4] Sedgewick, R. (1998). Algorithms in C parts 1-4. Fundamentals, data structures, sorting, searching. Addison-Wesley Publishing Company, Inc.
[5] Sedgewick, R. (2018). Algorithms, 4th Edition. Retrieved January 12, 2021, from
https://algs4.cs.princeton.edu/home/
