Алгоритм Дейкстры

Итеративный алгоритм

Алгоритм, предложенный Дейкстрой⁷⁾, настолько мощнее рекурсивного алгоритма Расст-Рек, что, при тех же начальных условиях и не прикладывая дополнительных усилий, он может найти расстояние от выделенной вершины s не только до одной вершины t, но и до всех остальных вершин графа.

Итак, пусть граф задан матрицей смежности.

Линейный массив dist будет хранить длины текущих путей от вершины s до всех остальных вершин. В начале этот массив будет инициирован числами MaxLongInt, символизирующими "бесконечность". По окончании работы алгоритма в этом массиве останутся только минимальные значения длин путей, которые и являются расстояниями.

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

Переменная last будет хранить номер последней помеченной вершины.

Отметим особо, что на каждом шаге Алгоритм Дейкстры находит длину кратчайшего пути до очередной вершины графа. Именно поэтому достаточно сделать ровно N-1 итераций.

1. Расстояние от s до s, конечно же, равно 0. Кроме того, это расстояние уже никогда не сможет стать меньше - ведь веса всех ребер графа у нас положительны. Таким образом:

dist[s]:= 0; done[s]:= true; last:= s;

2. Повторить N-1 раз следующие действия:

1. для всех непомеченных вершин х, связанных ребром с вершиной last, необходимо пересчитать расстояние:

dist[x]:= min(dist[x], dist[last]+ sm[last,x]);

1. среди всех непомеченных вершин найти минимум в массиве dist: это будет новая вершина last;
2. пометить эту новую вершину в массиве done.

Дата добавления: 2014-01-03