Combinatorial algorithm for finding the number of paths on a directed graph
- Authors: Erusalimskiy l.M.1, Cherdyntseva M.I.2
-
Affiliations:
- Южный федеральный университет
- Южный федеральный университета
- Issue: Vol 204 (2022)
- Pages: 37-43
- Section: Articles
- URL: https://ogarev-online.ru/2782-4438/article/view/269973
- DOI: https://doi.org/10.36535/0233-6723-2022-204-37-43
- ID: 269973
Cite item
Full Text
Abstract
In this paper, we present an algorithm for finding the number of paths on a directed graph that start at an arbitrary subset of its vertices. The algorithm is based on the ideas underlying the construction of Pascal’s triangle. The complexity of the algorithm coincides with the complexity of the well-known Dijkstra algorithm for finding shortest paths on graphs. We also generalize the algorithm proposed to the problem on graphs with reachability constraints.
Keywords
About the authors
la. M. Erusalimskiy
Южный федеральный университет
Author for correspondence.
Email: ymerusalimskiy@sfedu.ru
Russian Federation
M. I. Cherdyntseva
Южный федеральный университета
Email: micherdynceva@sfedu.ru
Russian Federation
References
- Басангова Е. О., Ерусалимский Я. М. Различные виды смешанной достижимости// в кн.: Алгебра и дискретная математика. — Элиста: КалмГУ, 1985. — С. 70-75.
- Басангова Е. О., Ерусалимский Я. М. Смешанная достижимость на частично ориентированных графах// в кн.: Вычислительные системы и алгоритмы. — Ростов-на-Дону: РГУ, 1983. — С. 135-140.
- Ерусалимский Я. М. 2-3 paths in a lattice graph. Random walks// Мат. заметки. — 2018. — 104, № 3. — С. 396-406.
- Ерусалимский Я. М. Дискретная математика. Теория и практикум. — СПб.: Лань, 2018.
- Ерусалимский Я. М. Треугольник Паскаля: комбинаторика и случайные блуждания. — М.: Вузовская книга, 2020.
- Ерусалимский Я. М., Петросян А. Г. Многопродуктовые потоки в сетях с нестандартной достижи мостью/ / Изв. вузов. Сев.-Кав. рег. Естеств. науки. Прилож. — 2005. — №6. — С. 8-16.
- Ерусалимский Я. М, Скороходов В. А. Общий подход к нестандартной достижимости на графах// Изв. вузов. Сев.-Кав. рег. Естеств. науки. — 2005. — Спецвыпуск. Псевдодифференциальные уравне ния и некоторые проблемы математической физики. — С. 64-67.
- Ерусалимский Я. М, Скороходов В. А. О потоках в сети с ограничениями на достижимость. Вычисли тельный эксперимент// Мат. Весенней Воронеж. мат. школы «Современные методы теории краевых задач» (Понтрягинские чтения-XXVI). — ВГУ, 2015. — С. 89-90.
- Ерусалимский Я. М, Скороходов В. А. Потоки в сетях со связанными дугами// Изв. вузов. Сев.-Кав. рег. Естеств. науки. Прилож. — 2003. — № 8. — С. 9-12.
- Ерусалимский Я. М, Скороходов В. А. Прибыль от потоков с обратной связью в орсетях с ограничениями на достижимость// Изв. вузов. Сев.-Кав. рег. Естеств. науки. Прилож. — 2003. — № 8. — С. 3-8.
- Ерусалимский Я. М, Скороходов В. А., Кузьминова М. В., Петросян А. Г. Графы с нестандартной достижимостью. Задачи, приложения. — Ростов-на-Дону: ЮФУ, 2009.
- Жилякова Л. Ю. Графовые динамические модели и их свойства// Автомат. телемех. — 2015. — 8. — С. 115-139.
- Dijkstra E. W. A note on two problems in connexion with graphs// Numer. Math. — 1959. — 1. — P. 269-271.
- Erusalimskiy I. M. Graph-lattice: random walk and combinatorial identities// Bol. Soc. Mat. Mexicana. — 2016. — 22, № 2. — P. 329-335.
Supplementary files
