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

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

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

1.всем вершинам приписывается вес - вещественное число, d(i):= GM для всех вершин кроме вершины с номером u1 , а d(u1):= 0 2.всем веpшинам приписывается метка 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), то путь не существует, покидаем алгоритм 6.иначе найденную вершину c минимальным весом полагаем текущей и помечаем (m(t):= 1) 7.если t = u2 , то найден путь веса d(t), покидаем алгоритм 8.переходим на шаг 4.

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

К сожалению, для данного алгоритма нет исходного кода. Это не ошибка и сообщать мне об этом не надо. Возможно, для алгоритма ещё не успели создать исходный код, или же при переносе алгоритма из старой версии библиотеки возникли проблемы с исходником и его написание пришлось отложить до лучших времен. Попробуйте воспользоваться прилагаемыми файлами и блок-схемой или поискать на сайте аналогичный алгоритм, но с исходником.