Алгоритми на графах та їх застосування
Keywords:
граф, алгоритм, оптимізація, пошук у ширину, Дейкстра, маршрутизація, аналіз мережAbstract
У публікації розглянуто ключові алгоритми на графах та їх фундаментальну роль у розв’язанні сучасних обчислювальних задач. Проаналізовано базові підходи до обробки графових структур, зокрема алгоритми пошуку в ширину (BFS) та глибину (DFS), а також методи знаходження найкоротших шляхів, зокрема алгоритм Дейкстри. Особливу увагу приділено практичному застосуванню цих алгоритмів у реальних системах: від GPS-навігації та оптимізації логістики до аналізу соціальних мереж.
References
Introduction to Algorithms / T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Cambridge: MIT Press, 2022. 1312 p. URL: https://mitpress.mit.edu/9780262046305
Kleinberg J., Tardos E. Algorithm Design. Boston: Pearson Education, 2021. 749 p.
Sedgewick R., Wayne K. Algorithms. Boston: Addison Wesley, 2022. 976 p. URL: https://algs4.cs.princeton.edu
Frieze A., Karonski M. Introduction to Random Graphs. Oxford: Oxford University Press, 2023. 456 p. URL: https://www.math.cmu.edu/~af1p/BOOK.pdf
Hamilton W. L. Graph Representation Learning. Cambridge: Cambridge University Press, 2023. 420 p. URL: https://www.cs.mcgill.ca/~wlh/grl_book/
Graph Neural Networks: A Review of Methods and Applications / Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, P. S. Yu. New York: Elsevier, 2023. 530 p. URL: https://arxiv.org/abs/2001.00595
Burachievsky O. V. Теорія графів та її застосування в інформатиці. Київ: КНЕУ, 2023. 278 с.
Козак С. М. Евристичні методи та алгоритми оптимізації графових структур. Київ: КПІ ім. І. Сікорського, 2022. 310 с.
Вороніна Л. Ю. Аналіз соціальних графів у цифрових системах. Одеса: Астропринт, 2024. 254 с.
Хоміч Ю. О. Хмарні обчислення та графові моделі аналізу даних. Київ: КНЕУ, 2022. 321 с.
Graph Algorithms Explained. GeeksforGeeks. 2024. URL: https://www.geeksforgeeks.org/graph-datastructure-and-algorithms/
Applications of Graph Theory in Computer Science / H. C. Martin, W. R. V. Sampaio, J. C. C. Verancio, R. S. Souza. Revista Indicação Geografica e Inovação. 2023. № 7(2). P. 2069–2078. URL: https://www.researchgate.net/publication/370515232
Graph Algorithms and Their Applications in Big Data. ScienceDirect. 2023. URL: https://www.sciencedirect.com/topics/computer-science/graph-algorithm
Shortest Path Algorithms: Dijkstra, Bellman-Ford A. Khan Academy. 2024. URL: https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation
CS224W: Machine Learning with Graphs. CS224W Course Materials. 2024. URL: https://web.stanford.edu/ class/cs224w/
Алгоритми на графах у Python. IT-Інфо. 2024. URL: https://itinfo.ua/articles/python-graph-algorithms
Graph Neural Networks: A Review of Methods and Applications Applications / Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, P. S. Yu. ScienceDirect. 2020. URL: https://www.sciencedirect.com/science/article/pii/S26666510 21000012
Kumar S., Patel N. Approximation Algorithms and Heuristics for Large-Scale Graph Problems. London: Academic Press, 2023. 388 p.
