Hello, Sly!

Tue Jul 01 1997, at 15:02, Sly Golovanov wrote All:

> Алгоритм Дейкстры нахождения кратчайшего пути в графе объясните
> кто-нибудь, плз. Hу не имею я доступа к библиотеке!

Деpжи цитату:
============================================================
Задача:
   В ориентированной, неориентированной или смешанной (т. е.
   такой, где часть дорог имеет одностороннее движение) сети V найти
   кратчайший путь из заданной вершины i во все остальные вершины.
Решение (Дейкстpа, 1959 г.)
   Алгоритм использует три массива из N (= числу вершин сети)
чисел каждый. Первый массив A содержит метки с двумя значения:
0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена);
второй массив B содержит расстояния - текущие кратчайшие рас-
стояния от до соответствующей вершины; третий массив с содержит
номера вершин - k-й элемент С[k] есть номер предпоследней вершины
на текущем кратчайшем пути из Vi в Vk. Матрица расстояний D[i,k] задает
длины дуге D[i,k]; если такой дуги нет, то D[i,k] присваивается большое число
Б, равное "машинной бесконечности".
   Теперь можно описать

   * Алгоритм Дейкстры *
1 (инициализация). В цикле от 1 до N заполнить нулями массив
A; заполнить числом i массив C; перенести i-ю строку матрицы
D в массив B,
   A[i]:=1; C[i]:=0 (i - номер стартовой вершины)
2 (общий шаг). Hайти минимум среди неотмеченных (т. е. тех k, для
которых A[k]=0); пусть минимум достигается на индексе j, т. е. B[j]<=B[k]
Затем выполняются следующие операции:
 A[j]:=1;
 если B[k]>B[j]+D[j,k], то (B[k]:=B[j]+D[j,k]; C[k]:=j)
(Условие означает, что путь Vi ... Vk длиннее, чем путь Vi...Vj Vk).
(Если все A[k] отмечены, то длина пути от Vi до Vk равна B[k]. Теперь
надо) перечислить вершины, входящие в кратчайший путь).
3 (выдача ответа). (Путь от Vi до Vk выдается в обратном порядке
следующей процедурой:)
3.1.  z:=C[k];
3.2.  Выдать z;
3.3.  z:=C[z]. Если z = О, то конец,
      иначе перейти к 3.2.

Для выполнения алгоритма нужно N раз просмотреть массив B
из N элементов, т. е. алгоритм Дейкстры имеет квадратичную
сложность: O(n2).
============================================================

Hа всякий случай деpжи еще и более общий алгоpитм Флойда-Уоpшелла --
находит кpатчайшие пути из всех во все:
============================================