Общая задача построения кратчайшего пути

 

Пусть, , – конечный связный орграф. Как и в предыдущем параграфе, каждой дуге поставлен соответствие вес дуги (здесь это число произвольное).

Постановка задачи. В заданной сети, найти путь минимальной длины между любой парой вершин или установить отсутствие пути.

Заметим, что если, то для решения можно использовать алгоритм Дейкстры, задав в качестве вершины s по очереди все имеющиеся вершины, т.е. алгоритм следует применить n раз.

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

В дальнейшем предполагаем, что в сети нет контуров отрицательного веса.

Указанную выше задачу хорошо решает алгоритм, предложенный Флойдом. Договоримся, что вершины сети перенумеруем элементами множества {1, 2, …, n}.

Алгоритм Флойда

Шаг 0. Формируем две n´ n-матрицы:

– матрица расстояний, где

(7.1)

– справочная матрица, где = i, .

Шаг k. Известны матрицы и. Находим матрицы, и =:

1) в матрице выделяем k-ый столбец и k-ую строку (назовем их базовыми),

2) вычисляем элементы новых матриц по правилу, используя элементы базовых строки и столбца:

если, то (7.2)

если, то (7.3)

Выход из алгоритма (принцип останова).

Если k = n + 1, то найденная матрица является матрицей искомых расстояний. Справочная матрица служит для определения вершин, через которые пройдет соответствующий минимальный путь. Значение показывает номер t вершины, предшествующей вершине j на пути из вершины i. Далее значение показывает номер вершины, предшествующий вершине t на пути из вершины i. И так далее, пока значение элемента i-ой строки не будет равно i.

Поясним смысл шага 1. Базовыми являются первая строка и первый столбец. Рассмотрим элемент матрицы, где. Согласно формулам (7.2) и (7.3) сравниваются две величины: – длина дуги непосредственно из вершины i в вершину j, и – длина «обходного» пути из вершины i в вершину j через вершину 1 (см. рис.7.1). Элементу присваивается значение, равное меньшему из сравниваемых величин. Очевидно, что при или (не существует «обходного» пути из вершины i в вершину j через вершину 1) значение =. В случае, когда, изменяется соответствующий элемент справочной матрицы: = 1. Так фиксируется вершина, через которую проходит «обходной» путь.

Теорема 1. Пусть – взвешенный орграф, в котором нет контуров отрицательной длины. Если в матрице элемент, то

а) есть длина минимального пути из вершины i в вершину j, где промежуточными вершинами являются вершины из;

б) в матрице элемент – номер вершины, которая непосредственно предшествует вершине j на пути из i в j.

Доказательство. Пусть k – некоторое целое неотрицательное число, не большее. В соответствие ему поставим множество вершин.

Построим матрицу истинно кратчайших расстояний из каждой вершины i в каждую вершину j, , , где промежуточными вершинами пути являются вершины из, следующим образом.

Если k = 0, то множество промежуточных вершин пусто, положим =.

Пусть k > 0. Для пары вершин i и j, , строим все пути (если они существуют) из i в j такие, что промежуточными вершинами могут быть лишь вершины из множества, сравниваем длины всех построенных путей, выбираем наименьшее значение. Это значение и есть элемент матрицы. Если же указанного выше пути не существует, то полагаем = ¥.

Докажем, что =, где матрица определена на k-том шаге алгоритма Флойда.

Воспользуемся методом математической индукции по числу k, .

Пусть k = 1. Тогда для пары вершин i и j соответствующий элемент матрицы есть длина минимального пути из вершины i в вершину j, где промежуточной вершиной может быть вершина 1. Другими словами, следует рассмотреть пути вида или. Следовательно, элемент матрицы совпадет с соответствующим элементом матрицы(см. пояснения к шагу 1 и рис.7.1).

Пусть утверждение справедливо для.

Докажем его для. Согласно алгоритму Флойда элементы матриц и находим либо по формуле (7.2):

, (7.4)

либо по формуле (7.3):

, . (7.5)

Базовыми являются m-ая строка и m-ый столбец. Сравниваем две величины: – длина пути из вершины i в вершину j, и – длина «обходного» пути из вершины i в вершину j через вершину m (см. рис. 7.1). Причем по индуктивному предположению числа, , – длины кратчайших путей, где промежуточными вершинами могут быть вершины из множества. Понятно, что – длина самого короткого «обходного» пути из вершины i в вершину j через вершины из множества. Поэтому формулы (7.4) или (7.5) дают значение кратчайшего пути из вершины i в вершину j через вершины из множества.

Если значение определено по формуле (7.4), то изменяется соответствующий элемент справочной матрицы: . Таким способом фиксируется вершина, которая предшествует вершине j на новом «обходном» пути.

Ясно, что при или не существует «обходного» пути из вершины i в вершину j через вершину m.

Итак, =, т.е. =.

Теорема доказана.

Замечание. Если при формировании матрицы положить, то на k-том шаге алгоритма Флойда элемент ¹ ¥ матрицы равен длине кратчайшего контура (если он существует), проходящего через вершину i и вершины множества. Поэтому алгоритм Флойда можно использовать для нахождения кратчайших контуров (если они существуют), проходящих через вершины данного орграфа. Значения ¹ ¥ и есть искомые величины. По справочной матрице находим вершины, через которые проходит контур. Понятно, что если в исходном графе существуют контуры отрицательной длины, то на некотором шаге появятся отрицательные диагональные элементы.

Итак, алгоритм Флойда может быть использован для нахождения контуров отрицательного веса. Если же поставлена задача нахождения пути минимальной длины между любой парой вершин, и на некотором шаге появился отрицательный диагональный элемент, то это признак того, что исходная задача не корректна, решение должно быть прекращено. Понятно, что если некоторый маршрут содержит контур отрицательной длины, то его длину можно сделать как угодно малой.

Пример 1. На сети, представленной на рис. 7.2, найти кратчайший путь (если он существует) между любой парой вершин.

Итерация 0.Строим матрицы и:

= =, = =.

Итерация 1. В полученной матрице выделяем первую строку и первый столбец. Для всех элементов матрицы, где, имеем. Поэтому и.

Итерация 2. В матрице выделяем вторую строку и второй столбец. Поскольку во втором столбце, , то строки с этими номерами не изменятся. Аналогично, во второй строке, , поэтому не изменятся элементы первого и пятого столбцов. Значит, следует пересчитать элементы, , , , :

= min(3; 7+3) = 3 =;

= min(8; 7+1) = 8 =;

= min(¥; 7+2) = 9 ¹ , = 2;

= min(¥; 4+3) = 7 ¹ , = 2;

= min(¥; 4+1) = 5 ¹ , = 2;

= min(0; 4+2) = 0 =.

Таким образом,

= , =

Итерация 3. Базовыми являются третья строка и третий столбец. Не изменяются базовые строка и столбец, а также первый, второй и шестой столбцы и четвертая строка. Результат пересчета остальных элементов – матрицы и:

= , =

Итерация 4. Базовыми являются четвертая строка и четвертый столбец. Не изменяются базовые строка и столбец, а также первый, второй, третий столбцы. Результат пересчета остальных элементов – матрицы и:

= , = .

Итерация 5. Базовыми являются пятая строка и пятый столбец. Не изменяются базовые строка и столбец, а также первый, второй столбцы. Результат пересчета остальных элементов – матрицы и:

= , = .

Итерация 6. Базовыми являются шестая строка и шестой столбец. Не изменяются базовые строка и столбец, а также первый столбец. Результат пересчета остальных элементов – матрицы и:

= , = .

Матрицы и являются искомыми. Например, кратчайшее расстояние из вершины 6 в вершину 3 равно = 7. Путь проходит через вершины (указываем в обратном порядке) 3, 2 (элемент ), 6 (элемент ).

Пример 2. На сети, представленной на рис. 7.3, найти контуры отрицательной длины, если они существуют.

Итерация 0.Строим матрицы и:

= =, = =.

 

Итерация 1. Как и в предыдущем примере, для всех элементов матрицы, где, имеем. Поэтому и.

Итерация 2.

= , = .

Итерация 3.

= , = .

Итерация 4.

= , = .

Поскольку = –12, то через вершину 6 проходит контур отрицательной длины, причем вершины этого контура из множества {2, 4}. Действительно, так как = 4, = 2, = 6, то контур состоит из дуг (6, 2), (2, 4), (4, 6).

Итерация 5.

= , = .

Итерация 6.

= , = .

В сети имеется контур отрицательной длины, который проходит через вершину 3, поскольку = –1.

⇐ Предыдущая123456Следующая ⇒

Поделиться: