Алгоритм дейкстры программа. Алгоритм дейкстры нахождения кратчайшего пути
Алгоритм Дейкстры – алгоритм на графах, который находит кратчайший путь между двумя данными вершинами в графе с неотрицательными длинами дуг. Также часто ставится задача расчёта кратчайшего пути от данной вершины до всех остальных. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации.
Описание
На вход алгоритма подаётся взвешенный ориентированный граф с дугами неотрицательного веса. На выходе получается набор кратчайших путей от данной вершины до других.
В начале расстояние для начальной вершины полагается равным нулю, а расстояния до всех остальных понимаются бесконечными. Массив флагов, обозначающих то, пройдена ли вершина, заполняется нулями. Затем на каждом шаге цикла ищется вершина с минимальным расстоянием до изначальной и флагом равным нулю. Для неё устанавливается флаг и проверяются все соседние вершины. Если рассчитанное ранее расстояние от исходной вершины до проверяемой больше, чем сумма расстояния до текущей вершины и длины ребра от неё до проверяемой вершины, то расстояние до проверяемой вершины приравниваем к расстоянию до текущей+ребро от текущей до проверяемой. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда расстояние до всех вершин c флагом 0 бесконечно. Последний случай возможен тогда и только тогда, когда граф несвязеный.
Алгоритм Дейкстры в псевдокоде
Вход: С : array of real – матрица длин дуг графа; s – вершина, от которой ищется кратчайший путь и t – вершина, к которой он ищется.
Выход: векторы Т: array of real; и Н: array of 0..р. Если вершина v лежит на кратчайшем пути от s к t, то T[v] - длина кратчайшего пути от s к у; Н[у] - вершина, непосредственно предшествующая у на кратчайшем пути.
Н – массив, в котором вершине n соответствует вершина m, предыдущая на пути к n от s.
T – массив, в котором вершине n соответствует расстояние от неё до s.
X – массив, в котором вершине n соответствует 1, если путь до неё известен, и 0, если нет.
инициализация массивов:
for v from 1 to р do
Т[ v ]: = ∞ { кратчайший путь неизвестен }
X[v]: = 0 { все вершины не отмечены}
H[s]: = 0 { s ничего не предшествует }
T[s] : = 0 { кратчайший путь имеет длину 0...}
X[s] : = 1 { ...и он известен } v : = s { текущая вершина }
М: { обновление пометок }
for и ∈ Г(и ) do
if Х[и] = 0 & Т[и] > T[v] + C then
Т[и] : = T[v] + C { найден более короткий путь из s в и через v }
H[u]: = v { запоминаем его }
m : = ∞
v : = 0
{ поиск конца кратчайшего пути }
for и from 1 to p do
if X[u] = 0 &T[u] < t then
v: = u ;
m: = T[u] { вершина v заканчивает кратчайший путь из s
if v = 0 then
stop { нет пути из s в t } end if
if v = t then
stop { найден кратчайший путь из s в t } end if
X[v]: = 1 { найден кратчайший путь из s в v } goto M
Обоснование
Для доказательства корректности алгоритма Дейкстры достаточно заметить, что при каждом выполнении тела цикла, начинающегося меткой М, в качестве v используется вершина, для которой известен кратчайший путь из вершины s. Другими словами, если X[v] = 1, то T[v] = d(s,v), и все вершины на пути (s,v), определяемом вектором Н, обладают тем же свойством, то есть
Vu Т[и] = 1 => Т[и] = d(s,u)&T] = 1.
Действительно (по индукции), первый раз в качестве v используется вершина s, для которой кратчайший путь пустой и имеет длину 0 (непустые пути не могут быть короче, потому что длины дуг неотрицательны). Пусть Т[u] = d(s,u) для всех ранее помеченных вершин и. Рассмотрим вновь помеченную вершину v , которая выбрана из условия T[v] = min Т[и]. Заметим, что если известен путь, проходящий через помеченные вершины, то тем самым известен кратчайший путь. Допустим (от противного), что T[v]> d(s, v), то есть найденный путь, ведущий из s в v, не является кратчайшим. Тогда на этом пути должны быть непомеченные вершины. Рассмотрим первую вершину w на этом пути, такую что T[w]= 0.Имеем: T[w]= d(s,w)⩽d(s>v) < Т[v],что противоречит выбору вершины u.
Временная сложность
Сложность алгоритма Дейкстры зависит от способа нахождения не посещённой вершины с минимальным расстоянием до изначальной, способа хранения множества непосещённых вершин и способа обновления меток. Пусть n количество вершин, а через m - количество рёбер в графе. Тогда в простейшем случае, когда для поиска вершины с минимальным расстоянием до изначальной вершины просматривается всё множество вершин, а для хранения расстояний используется массив, время работы алгоритма - О(n 2). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций. На циклы по соседям каждой посещаемой вершины тратится количество операций, пропорциональное количеству рёбер m (поскольку каждое ребро встречается в этих циклах ровно дважды и требует константное число операций). Таким образом, общее время работы алгоритма O(n 2 +m), но, так как m много меньше n(n-1), в конечном счёте получается О(n 2).
Для разреженных графов (то есть таких, для которых m много меньше n²) непосещённые вершины можно хранить в двоичной куче, а в качестве ключа использовать значения расстояний. Так как цикл выполняется порядка n раз, а количество релаксаций (смен меток) не больше m, время работы такой реализации - О(nlogn+mlogn)
Пример
Вычисление расстояний от вершины 1 по проходимым вершинам:
Алгоритм Дейкстры (англ. Dijkstra’s algorithm) - алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.
Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке.
Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.
Кружками обозначены вершины, линиями - пути между ними (рёбра графа). В кружках обозначены номера вершин, над рёбрами обозначена их «цена» - длина пути. Рядом с каждой вершиной красным обозначена метка - длина кратчайшего пути в эту вершину из вершины 1.
Первый шаг . Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.
Первый по очереди сосед вершины 1 - вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме значения метки вершины 1 и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.
Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й.
Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.
Второй шаг . Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещённых вершин. Это вершина 2 с меткой 7.
Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.
Первый (по порядку) сосед вершины 2 - вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.
Следующий сосед вершины 2 - вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а это меньше 17, поэтому метка не меняется.
Ещё один сосед вершины 2 - вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояния до 2-й вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22). Поскольку 22<, устанавливаем метку вершины 4 равной 22.
Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещённую.
Третий шаг . Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:
Дальнейшие шаги . Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.
Завершение выполнения алгоритма . Алгоритм заканчивает работу, когда нельзя больше обработать ни одной вершины. В данном примере все вершины зачёркнуты, однако ошибочно полагать, что так будет в любом примере - некоторые вершины могут остаться незачёркнутыми, если до них нельзя добраться, т. е. если граф несвязный. Результат работы алгоритма виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.
Реализация алгоритма на различных языках программирования:
C++
#include "stdafx.h" #includePascal
program DijkstraAlgorithm; uses crt; const V=6; inf=100000; type vektor=array of integer; var start: integer; const GR: array of integer=((0, 1, 4, 0, 2, 0), (0, 0, 0, 9, 0, 0), (4, 0, 0, 7, 0, 0), (0, 9, 7, 0, 0, 2), (0, 0, 0, 0, 0, 8), (0, 0, 0, 0, 0, 0)); {алгоритм Дейкстры} procedure Dijkstra(GR: array of integer; st: integer); var count, index, i, u, m, min: integer; distance: vektor; visited: array of boolean; begin m:=st; for i:=1 to V do begin distance[i]:=inf; visited[i]:=false; end; distance:=0; for count:=1 to V-1 do begin min:=inf; for i:=1 to V do if (not visited[i]) and (distance[i]<=min) then begin min:=distance[i]; index:=i; end; u:=index; visited[u]:=true; for i:=1 to V do if (not visited[i]) and (GR<>0) and (distance[u]<>inf) and (distance[u]+GRJava
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Solution { private static int INF = Integer.MAX_VALUE / 2; private int n; //количество вершин в орграфе private int m; //количествое дуг в орграфе private ArrayListЕщё один вариант:
Import java.io.*;
import java.util.*;
public class Dijkstra {
private static final Graph.Edge GRAPH = {
new Graph.Edge("a", "b", 7),
new Graph.Edge("a", "c", 9),
new Graph.Edge("a", "f", 14),
new Graph.Edge("b", "c", 10),
new Graph.Edge("b", "d", 15),
new Graph.Edge("c", "d", 11),
new Graph.Edge("c", "f", 2),
new Graph.Edge("d", "e", 6),
new Graph.Edge("e", "f", 9),
};
private static final String START = "a";
private static final String END = "e";
public static void main(String args) {
Graph g = new Graph(GRAPH);
g.dijkstra(START);
g.printPath(END);
//g.printAllPaths();
}
}
class Graph {
private final Map
C
#includePHP
$edge, "cost" => $edge); $neighbours[$edge] = array("end" => $edge, "cost" => $edge); } $vertices = array_unique($vertices); foreach ($vertices as $vertex) { $dist[$vertex] = INF; $previous[$vertex] = NULL; } $dist[$source] = 0; $Q = $vertices; while (count($Q) > 0) { // TODO - Find faster way to get minimum $min = INF; foreach ($Q as $vertex){ if ($dist[$vertex] < $min) { $min = $dist[$vertex]; $u = $vertex; } } $Q = array_diff($Q, array($u)); if ($dist[$u] == INF or $u == $target) { break; } if (isset($neighbours[$u])) { foreach ($neighbours[$u] as $arr) { $alt = $dist[$u] + $arr["cost"]; if ($alt < $dist[$arr["end"]]) { $dist[$arr["end"]] = $alt; $previous[$arr["end"]] = $u; } } } } $path = array(); $u = $target; while (isset($previous[$u])) { array_unshift($path, $u); $u = $previous[$u]; } array_unshift($path, $u); return $path; } $graph_array = array(array("a", "b", 7), array("a", "c", 9), array("a", "f", 14), array("b", "c", 10), array("b", "d", 15), array("c", "d", 11), array("c", "f", 2), array("d", "e", 6), array("e", "f", 9)); $path = dijkstra($graph_array, "a", "e"); echo "path is: ".implode(", ", $path)."\n";
Python
from collections import namedtuple, queue
from pprint import pprint as pp
inf = float("inf")
Edge = namedtuple("Edge", "start, end, cost")
class Graph():
def __init__(self, edges):
self.edges = edges2 =
self.vertices = set(sum(( for e in edges2), ))
def dijkstra(self, source, dest):
assert source in self.vertices
dist = {vertex: inf for vertex in self.vertices}
previous = {vertex: None for vertex in self.vertices}
dist = 0
q = self.vertices.copy()
neighbours = {vertex: set() for vertex in self.vertices}
for start, end, cost in self.edges:
neighbours.add((end, cost))
#pp(neighbours)
while q:
u = min(q, key=lambda vertex: dist)
q.remove(u)
if dist[u] == inf or u == dest:
break
for v, cost in neighbours[u]:
alt = dist[u] + cost
if alt < dist[v]: # Relax (u,v,a)
dist[v] = alt
previous[v] = u
#pp(previous)
s, u = deque(), dest
while previous[u]:
s.pushleft(u)
u = previous[u]
s.pushleft(u)
return s
graph = Graph([("a", "b", 7), ("a", "c", 9), ("a", "f", 14), ("b", "c", 10),
("b", "d", 15), ("c", "d", 11), ("c", "f", 2), ("d", "e", 6),
("e", "f", 9)])
pp(graph.dijkstra("a", "e"))
Output:
["a", "c", "d", "e"]
Для начала рассмотрим алгоритм Фалкерсона (графический способ упорядочивания элементов):
- 1. Найти вершины графа, в которые не входит не одна дуга. Они образуют первую группу. Пронумеровать вершины группы в произвольном порядке.
- 2. Вычеркнуть все пронумерованные вершины и дуги, из них исходящие. В получившемся графе найдется, по крайней мере, одна вершина, в которую не входит ни одна дуга. Этой вершине, входящей во вторую группу, присвоить очередной номер, и т. д. Второй шаг повторять до тех пор, пока не будут упорядочены все вершины.
Теперь рассмотрим алгоритм нахождения кратчайшего пути между двумя заданными вершинами в ориентированном графе. Пусть G = {S, U, ? } - ориентированный граф со взвешенными дугами. Обозначим s-вершину - начало пути и t-вершину - конец пути.
Алгоритм Дейкстры содержит одно ограничение - веса дуг должны быть положительными. Сам алгоритм состоит из двух этапов. На первом находится длина кратчайшего пути, на втором строится сам путь от вершины s к вершине t.
Этап 1. Нахождение кратчайшего пути.
Шаг 1. Присвоение вершинам начальных меток.
Полагаем d(s)=0* и считаем эту метку постоянной (постоянные метки помечаются сверху звёздочкой). Для остальных вершин x i S, x i ?s полагаем d(x i) = ? и считаем эти метки верными. Пусть x” = s, x” - обозначение текущей вершины.
Шаг 2. Изменение меток.
Для каждой вершины x i с временной меткой, непосредственно следующей за вершиной x”, меняем ее метку в соответствии со следующим правилом:
d нов. (x i) = min{d стар. (x i), d(x”)+щ(x”, x i)}.(1. 6. 1)
Шаг 3. Превращение метки из временной в постоянную.
Из всех вершин с временными метками выбираем вершину x j * с наименьшим значением метки
d(x j *) = min {d(x j) / x j S, d(x j) - временная}. (1. 6. 2)
Превращаем эту метку в постоянную и полагаем x” = x j *.
Шаг 4. Проверка на завершение первого этапа.
Если x” = t, то d(x”) - длина кратчайшего пути от s до t. В противном случае происходит возвращение ко второму шагу.
Этап 2. Построение кратчайшего пути.
Шаг 5. Последовательный поиск дуг кратчайшего пути.
Среди вершин, непосредственно предшествующих вершине x” c постоянными метками, находим вершину x i , удовлетворяющую соотношению
d(x”) = d(x i) + щ(x i , x”).(1. 6. 3)
Включаем дугу (x i , x”) в искомый путь и полагаем x” = x i .
Шаг 6. Проверка на завершение второго этапа.
Если x” = s, то кратчайший путь найден - его образует последовательность дуг, полученных на пятом шаге и выстроенных в обратном порядке. В противном случае возвращаемся к пятому шагу.
Пример 8: Задана весовая матрица? графа G. Найти минимальный путь из вершины x 1 в вершину x6 по алгоритму Дейкстры.
На рисунке 1. 11 изображён сам граф по данной матрице весов. Поскольку на данном графе есть цикл между вершинами x 2 , x 3 и x 5 , то вершины графа нельзя упорядочить по алгоритму Фалкерсона. На рисунке графа временные и постоянные метки указаны над соответствующей вершиной. Итак, распишем подробно работу алгоритма Дейкстры по шагам.
Шаг 1. Полагаем d(x 1) = 0*, x” = x 1 , d(x 2) = d(x 3) = d(x 4) = d(x 5) = d(x 6) = ?.
1-ая итерация.
Шаг 2. Множество вершин, непосредственно следующих за x” = x1 со временными метками S” = {x 2 , x 4 , x 5 }. Пересчитываем временные метки вершин: d(x 2) = min{?, 0*, + 9} = 9, d(x 4) = min{?, 0* + 6} = 6, d(x 5) = min{?, 0* + 11} = 11.
Шаг 3. Одна из временных меток превращается в постоянную min{9, ?, 6, 11, ?} = 6* = d(x 4), x” = x 4 .
Шаг 4. x” = x 4 ? t = x 6 , происходит возвращение на второй шаг.
2-ая итерация.
Шаг 2. S” = {x 2 , x 3 , x 5 }, d(x 2) = min{9, 6* + 5} = 9, d(x 3) = min {?, 6* + 7} = 13, d(x 5) = min{11, 6* + 6} = 11.
Шаг 3. min{d(x 2), d(x 3), d(x 5), d(x 6)} = min{9, 13, 11, ?} = 9* = d(x 2), x” = x 2 .
Шаг 4. x 2 ? x 6 , возвращение на второй шаг.
3-я итерация.
Шаг 2. S” ={x 3 }, d(x 3) = min{13, 9* + 8} = 13.
Шаг 3. min{d(x 3), d(x 5), d(x 6)} = min{31, 11, ?} = 11* = d(x 5), x” = x 5 .
Шаг 4. x 5 ? x 6 , возвращение на второй шаг.
4-ая итерация.
Шаг 2. S”={x 6 }, d(x 6) = min{?, 11* + 4} = 15.
Шаг 3. min {d(x 3), d(x 6)} = min{13, 15} = 13* = d(x 3), x” = x 3 .
Шаг 4. x 3 ? x 6 , возвращение на второй шаг.
5-ая итерация.
Шаг 2. S” = {x 6 }, d(x 6) = min{15, 13* + 9} = 15.
Шаг 3. min{d(x 6) } = min{15} = 15*, x” = x 6 .
Шаг 4. x 6 = t = x 6 , конец первого этапа.
Шаг 5. Составим множество вершин, непосредственно предшествующих x” = x 6 с постоянными метками S” = {x 3 , x 5 }. Проверим для этих двух вершин выполнение равенства d нов. (x i) = min{d стар. (x i), d(x”) + щ(x”, x i)}:
d(x”) = 15 = 11* + 4 = d(x 5) + щ(x 5 , x 6),
d(x”) = 15 ? 13* + 9 = d(x 3) + щ(x 3 , x 6).
Включаем дугу (x 5 , x 6) в кратчайший путь. x” = x 5 .
Шаг 6. x” ? s = x 1 , возвращение на пятый шаг.
2-ая итерация.
Шаг 5. S” = {x 1 , x 4 }.
d(x”) = 11 = 0* + 11 = d(x 1) + щ(x 1 , x 5),
d(x”) = 11 ? 6* + 6 = d(x 4) + щ(x 4 , x 5).
Включаем дугу (x 1 , x 5) в кратчайший путь. x” = x 1 .
Шаг 6. x” = s = x 1 , завершение второго этапа.
Итак, кратчайший путь от вершины x 1 до вершины x 6 построен. Его длина (вес) равна 15, сам путь образует следующая последовательность дуг: м = (x 1 , x 5) - (x 5 , x 6).
До каждого города области (если двигаться можно только по дорогам).
Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула .
Формальное определение
Пример
Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке.
Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.
Реализации на языках программирования
Исполнение в языке С(Си)
#define SIZE 6 #define INF 1000000000 int a [ SIZE ][ SIZE ] = {{ INF , 5 , INF , INF , INF , INF },{ 1 , 2 , 3 , 4 , 5 , 6 }, // матрица путей { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }, // индексы по горизонтали из точки { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }}; // по вертикали в точку, значение - вес int d [ SIZE ]; // массив найденных кратчайших путей, индексы - вершины графа void deikstra () { int v [ SIZE ]; // массив меток int temp , i ; int minindex , min ; for (i = 0 ; i < SIZE ; i ++ ) { d [ i ] = INF ; // массив путей инициализируется бесконечностью v [ i ] = 1 ; } d [ 0 ] = 0 ; do { // исполнение алгоритма minindex = INF ; min = INF ; for (i = 0 ; i < SIZE ; i ++ ) { if ((v [ i ] == 1 ) && (d [ i ] < min )) { min = d [ i ]; minindex = i ; } } if (minindex != INF ) { for (i = 0 ; i < SIZE ; i ++ ) { if (a [ minindex ][ i ] > 0 ) { temp = min + a [ minindex ][ i ]; if (temp < d [ i ]) d [ i ] = temp ; } } v [ minindex ] = 0 ; } } while (minindex < INF ); }
) выполняется за время O(m + n \ln n) и является асимптотически быстрейшим из известных последовательных алгоритмов для данного класса задач.
1.2 Математическое описание алгоритма
Пусть задан граф G = (V, E) с весами рёбер f(e) и выделенной вершиной-источником u . Обозначим через d(v) кратчайшее расстояние от источника u до вершины v .
Пусть уже вычислены все расстояния, не превосходящие некоторого числа r , то есть расстояния до вершин из множества V_r = \{ v \in V \mid d(v) \le r \} . Пусть
(v, w) \in \arg\min \{ d(v) + f(e) \mid v \in V, e = (v, w) \in E \}.Тогда d(w) = d(v) + f(e) , и v лежит на кратчайшем пути от u к w .
Величины d^+(w) = d(v) + f(e) , где v \in V_r , e = (v, w) \in E , называются предполагаемыми расстояниями и являются оценкой сверху для настоящих расстояний: d(w) \le d^+(w) .
Алгоритм Дейкстры на каждом шаге находит вершину с наименьшим предполагаемым расстоянием, помечает её как посещённую и обновляет предполагаемые расстояния для всех концов рёбер, исходящих из неё.
1.3 Вычислительное ядро алгоритма
Основные вычисления связаны с операциями над очередью с приоритетом:
- извлечение минимального элемента (delete_min);
- уменьшение приоритета элемента (decrease_key).
1.4 Макроструктура алгоритма
Псевдокод алгоритма:
Входные данные : граф с вершинами V , рёбрами E с весами f (e ); вершина-источник u . Выходные данные : расстояния d (v ) до каждой вершины v ∈ V от вершины u . Q := new priority queue for each v ∈ V : if v = u then d (v ) := 0 else d (v ) := ∞ Q .insert(v , d (v )) while Q ≠ ∅: v := Q .delete_min() for each e = (v , w ) ∈ E : if d (w ) > d (v ) + f (e ): d (w ) := d (v ) + f (e ) Q .decrease_key(w , d (w ))1.5 Схема реализации последовательного алгоритма
Конкретная реализация алгоритма Дейкстры определяется выбором используемого алгоритма очереди с приоритетом. В простейшем случае это может быть массив или список, поиск минимума в котором требует просмотра всех вершин. Более эффективным является использование кучи; наилучшую известную оценку сложности имеет вариант с использованием фибоначчиевой кучи .
Возможен вариант реализации, когда вершины добавляются в очередь не на этапе инициализации, а в момент первого посещения.
1.6 Последовательная сложность алгоритма
Последовательная сложность алгоритма равна O(C_1 m + C_2n) , где
- C_1 – количество операций уменьшения расстояния до вершины;
- C_2 – количество операций вычисления минимума.
Оригинальный алгоритм Дейкстры использовал в качестве внутренней структуры данных списки, для которых C_1 = O(1) , C_2 = O(n) , так что общая сложность составляла O(n^2) .
При использовании фибоначчиевой кучи время вычисления минимума сокращается до C_2 = O(\ln n) , так что общая сложность равна O(m + n \ln n) , что является асимптотически наилучшим известным результатом для данного класса задач.
1.7 Информационный граф
Приводится граф алгоритма для базовой реализации алгоритма Дейкстры на списках или массивах.
Рисунок 1. Граф алгоритма без отображения входных и выходных данных. n=3. Желтым цветом обозначены операции сравнения, зеленым - операции изменения меток вершин, синим - пометка вершины.
1.8 Ресурс параллелизма алгоритма
Алгоритм Дейкстры допускает эффективную параллелизацию , среднее время работы O(n^{1/3}\ln n) с объёмом вычислений O(n \ln n + m) .
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
На рисунке 6 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность работы с памятью достаточно низка. Это неудивительно, поскольку реализации алгоритмов над графами почти всегда обладают низкой эффективностью вследствие нерегулярности доступа к данным, что мы и увидели при анализе профиля обращений.
Рисунок 6. Сравнение значений оценки daps
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.
На рисунке 7 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что в данном случае значение cvg хорошо коррелирует с оценкой производительности и отражает низкую локальность, что соответствует выводам, сделанным при качественной оценке локальности.
Рисунок 7. Сравнение значений оценки cvg
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.4.1 Масштабируемость алгоритма
2.4.2 Масштабируемость реализации алгоритма
Проведём исследование масштабируемости параллельной реализации алгоритма согласно методике . Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета . Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессоров со значениями квадрата целого числа;
- размер графа с шагом 16000.
На следующем рисунке приведен график производительности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.
Рисунок 8. Параллельная реализация алгоритма. Изменение производительности в зависимости от числа процессоров и размера области.
В силу особенностей параллельной реализации алгоритма производительность в целом достаточно низкая и с ростом числа процессов увеличивается медленно, а при приближении к числу процессов 128 начинает уменьшаться. Это объясняется использованием коллективных операций на каждой итерации алгоритма и тем, что затраты на коммуникационные обмены существенно возрастают с ростом числа использованных процессов. Вычисления на каждом процессе проходят достаточно быстро и потому декомпозиция графа слабо компенсирует эффект от затрат на коммуникационные обмены.
2.5 Динамические характеристики и эффективность реализации алгоритма
Для проведения экспериментов использовалась реализация алгоритма Дейкстры. Все результаты получены на суперкомпьютере "Ломоносов". Использовались процессоры Intel Xeon X5570 с пиковой производительностью в 94 Гфлопс, а также компилятор intel 13.1.0. На рисунках показана эффективность реализации алгоритма Дейкстры на 32 процессах.
Рисунок 9. График загрузки CPU при выполнении алгоритма Дейкстры
На графике загрузки процессора видно, что почти все время работы программы уровень загрузки составляет около 50%. Это указывает на равномерную загруженность вычислениями процессоров, при использовании 8 процессов на вычислительный узел и без использования Hyper Threading.
Рисунок 10. График операций с плавающей точкой в секунду при выполнении алгоритма Дейкстры
На Рисунке 10 показан график количества операций с плавающей точкой в секунду. На графике видна общая очень низкая производительность вычислений около 250 Kфлопс в пике и около 150 Кфлопс в среднем по всем узлам. Это указывает то, что в программе почти все вычисления производятся с целыми числами.
На графике записей в память видна похожая картина неравномерности вычислений, при которой одновременно активно выполняют запись только несколько процессов. Это коррелирует с другими графиками выполнения. Стоит отметить достаточно низкое число обращений на запись в память. Это указывает на хорошую организацию вычислений и достаточно эффективную работу с памятью.
Рисунок 15. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Дейкстры
На графике скорости передачи данных по сети Infiniband наблюдается достаточно высокая скорость передачи данных в байтах в секунду. Это говорит о том, что процессы между собой обмениваются интенсивно и вероятно достаточно малыми порциями данных, потому как производительность вычислений высока. Стоит отметить, что скорость передачи отличается между процессами, что указывает на дисбаланс вычислений.
Рисунок 16. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Дейкстры
На графике скорости передачи данных в пакетах в секунду наблюдается крайне высокая интенсивность передачи данных. Это говорит о том, что, вероятно, процессы обмениваются не очень существенными объемами данных, но очень интенсивно. Используются коллективные операции на каждом шаге с небольшими порциями данных, что объясняет такую картину. Также наблюдается меньший дизбаланс между процессами, чем наблюдаемый в графиках использования памяти, вычислений и передачи данных в байтах/сек. Это указывает на то, что процессы обмениваются по алгоритму одинаковым числом пакетов, однако получают разные объемы данных и ведут неравномерные вычисления.
Рисунок 17. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Дейкстры
На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно и приблизительно равняется 8. Это свидетельствует о стабильной работе программы с загруженными вычислениями всеми узлами. Это указывает на очень рациональную и статичную загрузку аппаратных ресурсов процессами. И показывает достаточно хорошую эффективность выполняемой реализации. В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала достаточно эффективно, и стабильно. Использование памяти очень интенсивное, а использование коммуникационной среды крайне интенсивное, при этом объемы передаваемых данных не являются высокими. Это указывает на требовательность к латентности коммуникационной среды алгоритмической части программы. Низкая эффективность связана, судя по всему, с достаточно высоким объемом пересылок на каждом процессе и с интенсивными обменами сообщениями.