Итеративный алгоритм
Для этого алгоритма удобно, чтобы граф был представлен списком ребер.
Массив mark, как и прежде, будет хранить номера компонент связностей, к которым принадлежат помеченные вершины графа.
Алгоритм, предложенный Дейкстрой2), настолько мощнее рекурсивного алгоритма Расст-Рек, что, при тех же начальных условиях и не прикладывая дополнительных усилий, он может найти расстояние от выделенной вершины s не только до одной вершины t, но и до всех остальных вершин графа.
Итак, пусть граф задан матрицей смежности.
Линейный массив dist будет хранить длины текущих путей от вершины s до всех остальных вершин. В начале этот массив будет инициирован числами MaxLongInt, символизирующими "бесконечность". По окончании работы алгоритма в этом массиве останутся только минимальные значения длин путей, которые и являются расстояниями.
Еще один линейный массив done потребуется нам для того, чтобы хранить информацию о том, найден ли уже минимальный путь (он же расстояние) до соответствующей вершины и можно ли исключить эту вершину из дальнейшего рассмотрения.
Переменная last будет хранить номер последней помеченной вершины.
Отметим особо, что на каждом шаге Алгоритм Дейкстры находит длину кратчайшего пути до очередной вершины графа. Именно поэтому достаточно сделать ровно N-1 итераций.
Для этого алгоритма удобно, чтобы граф был представлен списком ребер.
Массив mark, как и прежде, будет хранить номера компонент связностей, к которым принадлежат помеченные вершины графа.
