Алгоритмы на графах и их приложения. Дорофеева В.И. - 33 стр.

тельны. Путь ищется из вершины номер u1 к вершине номер u2. Процедура ис-
пользует алгоритм Дейкстры. Для бесконечности используется число 0.

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

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

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

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

     4.    для всех вершин, у которых m(i)=0, пересчитываем вес по формуле:
           d(i):=min{d(i), d(t)+W[t,i]};

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

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

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

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

     На выходе имеем переменную length, которая определяет длину пути
(length=-1 если пути не существует, length=0, если u1=u2), переменную Weight -
вес пути и массив Path, содержащий последовательность номеров вершин, оп-
ределяющих путь. В алгоритме не упомянуто, как же определить сам путь, но
это легко выяснить, если посмотреть блок-схему.
     Опишем алгоритм Дейкстры в приложении к конкретной задаче.
     Пусть необходимо найти минимальный путь в транспортной сети, графи-
ческое изображение которой представлено на Рисунке 34. Пусть узлом-
источником является вершина 1, узлом-стоком – вершина 6. Найдем минималь-
ный путь (F) между этими вершинами. Начальное значение F нулевое.

                                           33