Алгоритм Дейкстры
Алгоритм Дейкстры – алгоритм поиска кратчайшего расстояния от одной вершины графа до всех остальных. Перед началом работы каждой вершине приписывается её вес: для начальной вершины, для которой производится поиск расстояний, он равен нулю, для всех остальных – бесконечность. Затем инициализируется обход графа – обновляются веса всех смежных вершин, вес вычисляется исходя из длины ребра. После чего из смежных вершин выбирается та, вес которой минимален, она становится ключевой. К ключевой вершине повторяются все предыдущие действия, но вес рассчитывается из минимума нынешнего веса смежной вершины и суммы весов ключевой вершины и ребра, что соединяет её со смежной вершиной. Всё это повторяется до тех пор, пока не будет пройден весь граф и не будет найдено кратчайшее расстояние до каждой из вершин.
Сравнивая с алгоритмом Флойда-Уоршелла, алгоритм Дейкстры более частный, поскольку он находит кратчайшие расстояния только от одной вершины ко всем.
Пример работы
Дан взвешенный неориентированный граф:
Рис. 4. Граф, который обрабатывается алгоритмом Дейкстры.
Шаг 1. Вес всех вершин, кроме начальной (пусть будет 1), устанавливается равным бесконечности. Вес начальной вершины 1 устанавливается равным нулю.
Шаг 2. Вес вершин, которые смежные с начальной, обновляется: 2 : 5 5 : 3 3 : 7
Шаг 3. Следующей точкой для действий выбирается та, вес которой минимален. Это вершина 5. Обновляется вес вершин, которые смежны с вершиной 5 – в том случае, если старый вес больше, чем сумма веса вершины 5 и ребра, что соединяет вершину 5 со смежной вершиной: 2 : 4 4 : 5
Выбор ближайшей вершины
Обновление веса смежных вершин
Конец
Шаг
4. Все вершины посещены, алгоритм
прекращает свою работу. Затрачено 4
шага. Кратчайшие расстояния от вершины
1 до всех остальных вершин графа найдены
и равны:
1 – 2 : 4
1 – 3 : 7
1 – 4 : 5
1
– 5 : 3
Сравнение
Проведя сравнение времени, затрачиваемого на алгоритмы Флойда-Уоршелла и Дейкстры были получены следующие графики:
Время в нс
Количество вершин графа
На рисунке оранжевым цветом представлен алгоритм Дейкстры, синим – Флойда-Уоршелла. По графику видно, что при увеличении размерности матрицы смежности (то есть, при увеличении количества вершин графа) время, затрачиваемое на обработку алгоритмов, увеличивается тоже. Но стоит отметить, что на алгоритм Флойда-Уоршелла времени затрачивается много больше, нежели чем на алгоритм Дейкстры. Это связано с тем, что сложность алгоритма Флойда-Уоршелла сильно выше, чем алгоритма Дейкстры – (количество вершин)^3.
Это также подтверждается небольшим примером: в графе на 5 вершин на алгоритм Флойда-Уоршелла было затрачено 5 шагов, а на алгоритм Дейкстры – 4 шага.
Выводы
В ходе работы:
Изучены алгоритмы Флойда-Уоршелла и Дейкстры.
Составлена программа подсчета временных затрат с учетом требований по точности проводимых измерений и обладающая возможностью создать граф любой размерности и любого содержания.
Визуализированы полученные данные посредством диаграммы на Рис. 6.
Сделан вывод, что алгоритм Дейкстры быстрее алгоритма Флойда-Уоршелла ввиду того, что алгоритм Флойда обладает более высокой сложностью в любом случае – O(n^3), когда для алгоритма Дейкстры в самом неблагоприятном случае - O(n^2). Это же подтверждается количеством затраченных шагов для небольшого примера: 5 шагов для Флойда-Уоршелла и 4 шага для Дейкстры.