IX Международная студенческая научная конференция Студенческий научный форум - 2017

Алгоритмы поиска кратчайших путей на графах нашли свое применение в различных областях и сферах деятельности человека. Такие алгоритмы используются в картографических сервисах, при построении пути GPS-навигатора, для представления и анализа дорожной сети и во многих других областях [1]. При этом в настоящее время существует большое число алгоритмов и подходов, которые решают эту задачу. Кроме того, в большинстве своем алгоритмы можно логически разделить на два класса — алгоритмы поиска кратчайшего расстояния от одной вершины до всех остальных и алгоритмы поиска кратчайших расстоянии между каждой парой вершин [1].

С ростом многопроцессорных архитектур был получен мощный инструмент для эффективного расчета искомых расстояний — была получена возможность запускать эти алгоритмы на нескольких вычислительных ядрах. При этом в контексте с параллельными алгоритмами на графах встал вопрос об эффективном использовании ресурсов системы. Эта задача, однако, не имеет такого высокого разнообразия решений, как в случае однопоточного алгоритма. Существующие же решения довольно специфичны и не всегда работают эффективно на всех графовых структурах.

Целью данной работы является: анализ эффективности применения параллельных алгоритмов для поиска кратчайшего пути в графе.

Для достижения поставленной цели были решены следующие исследовательские задачи:

• Провести анализ видов графов, существующих параллельных алгоритмов поиска кратчайшего пути в графе.

• Составить математическое описание информационной системы поиска кратчайшего пути в графе с использованием параллельных алгоритмов.

• Выполнить программную реализацию информационной системы поиска кратчайшего пути в графе с использованием параллельных алгоритмов.

• Проверить эффективность реализованных алгоритмов информационной системы поиска кратчайшего пути в графе с использованием параллельных алгоритмов.

На рассмотрение были вынесены параллельные алгоритмы Флойда – поиск кратчайшего пути и последовательный алгоритм Прима – нахождение минимального охватывающего дерева. В дальнейшем планируется их реализация и выполнение их сравнительного анализа параллельных и последовательных алгоритмов.

Исходной информацией для задачи поиска кратчайшего пути является взвешенный граф G=(V,R), содержащий n вершин (|V|=n), в котором каждому ребру графа приписан неотрицательный вес. Граф будем полагать ориентированным, т.е. если из вершины i есть ребро в вершину j, то из этого не следует наличие ребра из j в i. В случае если вершины все же соединены взаимообратными ребрами, веса, приписанные им, могут не совпадать. Рассмотрим задачу, в которой для имеющегося графа G требуется найти минимальные длины путей между каждой парой вершин графа [2].

В заключении был выполнен анализ применение алгоритмов поиска кратчайшего пути в графах. Самым распространенным применением алгоритмов поиска кратчайшего пути в графе является их применение в системах навигации для построения маршрутов между несколькими точками, обозначающими физические объекты. Поэтому в данном разделе были рассмотрены следующие системы: Сервис GraphOnline, Пакет утилит Graphviz, Система neo4J, Система GraphX.

Библиографический список

1. Изотова Т. Ю.. Обзор алгоритмов поиска кратчайшего пути в графе // Новые информационные технологии в автоматизированных системах. 2016. №19 С.341-344.

2. Фам Конг Тханг, Нгуен Ван Хьеу Построение алгоритма поиска кратчайшего пути на расширенном графе // Известия ТулГУ. Технические науки. 2013. №11 С.367-372.

Код для цитирования: Скопировать