Теория и практика параллельных вычислений
Алгоритм Дейкстры поиска кратчайших путей
Задача поиска кратчайших путей на графе состоит в нахождении путей минимального веса от некоторой заданной вершины S до всех имеющихся вершин графа. Постановка подобной проблемы имеет важное практическое значение в различных приложениях, когда веса дуг означают время, стоимость, расстояние, затраты и т.п.
Возможный способ решения поставленной задачи, известный как алгоритм Дейкстры, практически совпадает с методом Прима. Различие состоит лишь в интерпретации и в правиле оценки расстояний. В алгоритме Дейкстры эти величины означают суммарный вес пути от начальной вершины до всех остальных вершин графа. Как результат, на каждой итерации алгоритма выбирается очередная вершина, расстояние от которой до корня дерева минимально, и происходит включение этой вершины в дерево кратчайших путей.
Задания и упражнения
- Запустите систему ПараЛаб. В активном окне вычислительного эксперимента установите топологию Полный граф. Текущей задачей этого окна сделайте задачу обработки графов.
- Выполните команду Формирование графа пункта меню Задача. В появившемся редакторе графов сформируйте случайным образом граф с десятью вершинами.
- Выполните вычислительный эксперимент по поиску минимального охватывающего дерева с помощью алгоритма Прима (выполните команду Метод пункта меню Задача, в появившемся диалоговом окне выберите Метод Прима).
- Проведите несколько экспериментов, изменяя количество процессоров. Изучите зависимость временных характеристик алгоритма Прима от количества процессоров.
- Проведите аналогичную последовательность экспериментов для изучения временных характеристик метода Дейкстры.
