Алгоритм Дейкстеры – поиск минимального пути на графе при не отрицательных весах ребер

Информация с Интуита…

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

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

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

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

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

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

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

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

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

Реализация

Мы надеемся, что функцию поиска меньшего из двух целых чисел min, использованную в тексте программы, читатели смогут написать самостоятельно.

 

Также…

Теория на Вики

Моя реализация (пока что на коленке)

Дейкстера, поиск минимального пути в графе (сам путь и его стоимость в моей реализации). Пусть есть граф, заданный матрицей смежности AAdjencyMatrix, размером ASizeOfMatrix. Необходимо найти минимальное расстояние и сам минимальный путь от одной вершины к другой. Я сделал это так… Код не тестил, на уровне идеи…

Реализация Дениса Кряжева

 

 

This entry was posted in Delphi. Bookmark the permalink.

Leave a Reply