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

Процедура находит путь минимального веса в графе 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 содержащий последовательность номеров вершин определяющих путь. В алгоритме не упомянуто, как же определить сам путь, но это легко выяснить, если посмотреть блок-схему.

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

2.3.Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин (алгоритм Флойда).

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

Следует заметить, что если в графе существует контур отрицательной суммарной длины, то вес любого пути, проходящего через вершину из этого контура, можно сделать сколь угодно малой, "прокрутившись" в контуре необходимое количество раз. Поэтому поставленная задача разрешима не всегда. В случае, описанном выше, алгоритм Флойда прекращает свою работу. Останавливаясь подробнее, надо заметить, что если граф неориентированный (W симметрична), то ребро с отрицательным весом является как раз таким контуром (туда-сюда можно бегать, пока не сделаем вес достаточно малым).

Алгоритм Флойда предполагает последовательное преобразование матрицы весов W. В конечном итоге получаем матрицу, элементы dij которые представляют из себя вес минимального пути соединяющего i и j вершины. Рассмотрим преобразования матрицы весов:

D0 = W

dm+1 [i, j] = min{dm [i, j], dm [i, m+1] + dm [m+1, j]}, i!= j

dm+1 [i, i] = 0

преобразование проделывается для m = 1,..., n, где n - мощность множества вершин графа. Если на некотором шаге получим отрицательное dm [i, m]+dm [m, i] для какого-нибудь i, то в графе существует контур отрицательного веса, проходящий через вершину i и задача не разрешима.

На выходе получаем матрицу D минимальных весов и матрицу P при помощи, которой можно восстановить путь минимального веса следующим образом: значение p[i, j] будет равно номеру предпоследней вершины в пути между i и j (либо p[i, j] равно i, если путь не существует). Переменная s на выходе равна единице, если алгоритм отработал полностью, и нулю, если в ходе работы алгоритма найден контур отрицательного веса.

Заметим, что если граф неориентированный, то W а также все матрицы получаемые в результате преобразований симметричны и, следовательно, достаточно вычислять только элементы расположенные выше главной диагонали.

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

Дата добавления: 2014-01-15