Алгоритм поиска кратчайших путей

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Лекция

Алгоритм поиска кратчайших путей

Запишем двойственную задачу по отношению к исходной (1)-(5). При этом в двойственной задаче столько же переменных, сколько ограничений в исходной, и столько же ограничений, сколько в исходной задаче переменных. Ограничения (2)-(4) записаны для каждого узла сети, поэтому в двойственной задаче будет содержаться n переменных, т.е. вектор двойственных переменных запишется:

.

Тогда двойственная ЗЛП будет иметь вид:

(6)

Здесь - вектор ограничений (2)-(4), в котором на r-том месте стоит 1, а на s-том стоит -1. - вектор коэффициентов в ограничениях (2)-(4), в котором на i-том месте стоит 1, а на j-том стоит -1. Двойственные переменные не ограничены по знаку. В скалярной форме (6) запишется:

скалярный вектор сеть двойственный

(7)

Также как и в методе потенциалов, одну из двойственных переменных можно назначить произвольно. Пусть . Для удобства записи сделаем замену: . Тогда задача (7) примет вид:

(8)

(9)

Таким образом, вместо исходной задачи (1)-(5) необходимо решить двойственную задачу (8)-(10). Для этого исходные данные записываются в следующую таблицу:

Клетки строк и столбцов заполняются величинами по мере решения задачи (8)-(10). Остальные клетки соответствуют дугам и заполняются значениями длин дуг . Оставшиеся клетки не заполняются и в расчетах не участвуют.

Вначале в строке и столбце с номерами r записываются нулевые значения . Далее последовательно заполняются элементы столбцов начиная с №1. Для определения элемента просматривается столбец №j и если в этом столбце существует хотя бы одна клетка с известным элементом и известным значением , то вычисляется:

Минимум берется среди всех клеток , для которых известны и . Найденные значения записываются в строке и столбце с номером j. Этот процесс продолжается до тех пор, пока не определится для конечного узла s искомого пути.

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

Если при просмотре столбцов с неизвестными значениями невозможно их определить, то это значит, что до этих узлов j не существует пути из узла r. Строки и столбцы, соответствующие узлу j, из таблицы вычеркиваются.

Пусть найдены все для конечных узлов . Далее поверяются условия оптимальности (9). При этом возможны 2 случая:

Для любых дуг справедливо неравенство . Это означает, что кратчайшие пути найдены.

Существует хотя бы одна дуга , для которой имеет место . Это означает, что решение задачи не найдено, и решение следует продолжить. Для этого в клетках столбцов и строк , не удовлетворяющих неравенству (9), вместо значений записываются исправленные значения .

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

Когда задача решена, то величины , соответствующие концам пути, определяют длину кратчайшего пути из r в s, т.е. .

Сам кратчайший путь, т.е. узлы, через которые он проходит, восстанавливается следующим образом: в столбце s находится клетка , для которой . Такая клетка обязательно существует. Дуга будет последним звеном искомого пути. Далее в столбце с номером находится клетка , для которой . Дуга будет предпоследним звеном цепи. Далее просматривается столбец и т.д. до тех пор, пока не найдется первое звено пути , для которого .

Таким образом, найден путь . Длина этого пути

Для доказательства того, что найденный путь действительно является кратчайшим, рассматривается любой произвольный путь для дуг которого выполняется неравенство (9), и доказывается, что его длина , т.е. .

Так как предполагается, что для дуг пути выполняются неравенства (9), то можно записать:

…

Если сложить левые и правые части этих неравенств, то можно записать . Таким образом . Что и требовалось доказать.

Пример.

Найти кратчайший путь на заданной транспортной сети из узла №3 в узлы №5 и №7.

r=3, s=5,7.

Полагаем сначала . Далее:

j=1, v=3, =2. .

j=2, v=1, =4. =2=6.

j=4, v=1, =1. =2=3.

j=5, v=6, =2. =6=8.

j=6, v=4, =7. =3=10.

j=7, v1=5, =4. =8=12

v2=6, =1. =10=11

=11.

Проверка на оптимальность:

(1,2): =4= 7. (4,6): =7=

(1,3): =-2< 8. (5,3): =-8<

(1,4): =1= 9. (5,4): =-5<

(2,5): =2= 10. (5,7): =3<

(3,1): =2= 11. (6,2): =-8<

(4,3): =-3< 12. (6,7): =1=

Условие оптимальности выполняется для всех . Длина пути ==11, ==8.

Восстановление пути:

Путь : (3,1,4,6,7)

Путь (3,1,2,5).

Размещено на Allbest.ru