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

Путь минимальной суммарной длины во взвешенном графе с неотрицательными весами. (Алгоритм Дейкстры)

Процедура находит путь минимального веса в графе G=(V,E) заданном весовой матрицей w у которой элемент wij равен весу ребра соединяющего i-ую и j-ую вершины. При этом предполагается, что все элементы wij неотрицательны. Путь ищется из вершины номер u1 к вершине номер u2. Процедура использует алгоритм Дейкстры. Для бесконечности используется число GM его можно задавать в зависимости от конкретной задачи.

Алгоритм, по которому происходит поиск, заключается в следующем:

всем вершинам приписывается вес - вещественное число, d(i)=GM для всех вершин кроме вершины с номером u1, а d(u1)=0;

всем вершинам приписывается метка m(i)=0;

вершина u1 объявляется текущей - t=u1

для всех вершин, у которых m(i)=0, пересчитываем вес по формуле:

d(i):=min{d(i), d(t)+W[t,i]}

среди вершин для которых выполнено m(i)=0 ищем ту, для которой d(i) минимальна, если минимум не найден, т.е. вес всех не "помеченных" вершин равен бесконечности (GM), то путь не существует; ВЫХОД;

иначе найденную вершину c минимальным весом полагаем текущей и помечаем (m(t)=1)

если t=u2, то найден путь веса d(t),ВЫХОД;

переходим на шаг 4.

На выходе имеем переменную length, которая определяет длину пути (length=-1, если пути не существует, length=0, если u1=u2), переменную Weight -вес пути и массив Path содержащий последовательность номеров вершин определяющих путь. В алгоритме не упомянуто, как же определить сам путь, но это легко выяснить, если посмотреть блок-схему.