Алгоритм решения задачи о кратчайшем пути

1. По заранее заданной сети выписывается матрица расстояний между всеми узлами сети. Если дуга, соединяющая узлы, отсутствует (отсутствует путь, ведущий из -го пункта в -й), то в матрице расстояний ставится знак запрета данного пути.

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

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

4. . Если , для которых , вычисляются новые значения , используя формулу . Меняются и для на . Повторяется п.2 с новыми значениями и .

5. Полученные определяют кратчайшее расстояние между узлами 1 и . По выделенным элементам матрицы выписывается кратчайший путь.

Пример. Рассмотримсеть

Сеть содержит циклы, возникающие из-за возможности двустороннего движения. Если дуга ориентирована, (т.е. движение одностороннее), расстояние в другом направлении полагается равным ¥.

Занесем данные в матрицу расстояний, где строка (столбец ) представляет узел (узел ).

i j
				¥
		¥
j

Исходные величины и определяются следующим образом. Пусть . При использовании формулы

осуществляется последовательное обращение к величинам и по мере того, как они становятся доступными.

При переходе к шагу 2 проводится проверка условия оптимальности путем сравнения с . При этом выделяются те элементы, для которых = .

i j
		2		11
			3		5	1
				¥
		¥
							10

В процессе реализации алгоритма обнаруживается, что условие оптимальности первый раз нарушается при для и 5. Величины и меняются следующим образом:

После этого повторяется шаг 2 с измененными значениями и

i j
		2
			3		5	1
				¥
									(8)
		¥					9		(4)
				5	1		10
				(8)	(4)

Из последней таблицы видно, что в новых изменениях нет необходимости, и поэтому последние измененные величины дают длину кратчайшего пути от 1 до . Кратчайшее расстояние между узлами 1 и 7 равно (=13).

Найдем участки кратчайшего пути между узлами 1 и 7. Определение участков пути должно начинаться с узла 7. Из столбца 7 видно, что равенство выполняется (подчеркнутый элемент) при и , т.е. либо узел 5, либо узел 6 соединены с 7 (альтернативные решения). Аналогичные исследования для 5 и 6 узлов дадут и . Будем продолжать эту процедуру до тех пор, пока не вернемся в первый узел.

Таким образом, кратчайший путь имеет вид:

УПРАЖНЕНИЯ

Задача 1. Для местного аэропорта приобретается дополнительный автокар. Через три года планируется установка механизированной погрузочной системы, после чего автокары станут ненужными. Тем не менее может оказаться выгодным заменить автокар через год или два года или даже осуществить две замены (через год и через два года ). В следующей таблице приведены полные расходы (с учетом стоимости эксплуатации и выручкой от продажи), связанные с покупкой автокара в конце года i и его продажей в конце года j .

Необходимо минимизировать расходы.

Сформулировать задачу как задачу выбора кратчайшего пути. Решить полученную задачу.

Задача 2. Адам Козлевич ежедневно ездит на работу на автомобиле. Закончив в свое время полный курс по теории исследования операций, он легко определил самый короткий путь от дома до работы. К сожалению, данный маршрут усиленно патрулируется нарядами полиции, и автомобиль Козлевича часто останавливают за превышение скорости (как ему кажется, не обоснованно). Таким образом, самый короткий путь оказался не самым быстрым. Поэтому А. Козлевич планирует разработать новый маршрут, на котором он имел бы самую высокую вероятность не быть остановленным полицией. Схема сети дорог, по которой Козлевич может добраться от дома до работы, показана на рисунке.

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