Алгоритм поиска кратчайших путей для разреженных графов большой размерности
| Jazyk: | ruština |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Zdroj: | Прикладная дискретная математика. |
| ISSN: | 2311-2263 2071-0410 |
| Popis: | Рассматривается задача поиска кратчайших путей между всеми вершинами взвешенного ненаправленного разреженного графа. Предлагается алгоритм «разборки и сборки графа», использующий решение задачи на графе малой размерности для получения решения для исходного графа. Приводится сравнение предлагаемого алгоритма с одним из быстрых классических алгоритмов на данных из открытого доступа. All-pairs shortest path problem on weighted undirected sparse graphs is considered. "Disassembly and assembly of graph" algorithm is proposed to obtain the solution of the problem for the given graph using the solution of the problem for a small-dimensional graph. The algorithm is compared with one of the fastest classic algorithms on public source data. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
