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

Начальный шаг. Полагаем l*(s): = 0, R: = { s }, l(j) = l_sj, если дуга (s, j) Î U и l(j) = ¥ в противном случае. Для всех вершин v(j) = s.

Общая итерация. Шаг 1. Пусть arg( l(j)) = i и вершина i имеет метку (l(i), k). Если l(k) = ¥ и R ¹ V - алгоритм заканчивает работу.

Если l (k) < ¥ полагаем R: =R È {i} и l*(i)= l(i), v*(i)= k.

Если R = V - алгоритм заканчивает работу.

Если R ¹V - переходим к шагу 2.

Шаг 2. Для всех j Ï R, таких, что (k, j) Î U полагаем

l(j): = [l*(i) + l_ij, l(j) ].

Если l(i) + l_ij < l(j), то v(j): = i; в противном случае v(j) не меняет­ся. Переходим к шагу 1 следующей итерации.

Рассмотрим итерацию, на которой алгоритм заканчивает работу. Это происходит на шаге 1, когда либо l(j) = ¥ для всех j Ï R и R ¹ V, либо R=V.

В первом случае ни одна дуга, начальной вершиной которой являются вершина множества R, не ведет в вершины, не принадлежащие этому мно­жеству, а значит, не существует путей, ведущих из вершины s в вершины, не принадлежащие множеству R.

Во втором случае все вершины получили постоянную метку (l*(i), v*(i)), т.е. найдены кратчайшие расстояния от вершины S ко всем остальным верши­нам сети.

Заметим, что алгоритм явно не указывает кратчайший путь к вершине, а только его длину. Но воспользовавшись второй частью метки: v*(i) - его легко восстановить. Действительно, v*(i) - номер предпоследней вершины в кратчайшем пути из S в i; пусть v*(i) = i_1.

Но v*(i₁) = i₂ - номер предпоследней вершины в кратчайшем пути из S в i₁. Продолжая, мы найдем последовательность вершин S, i_k, i_k-1,..., i_2, i_1, k, через которые проходит кратчайший путь.

Рассмотрим работу алгоритма на следующем примере.

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

 

Рис.7

 

На начальном плане вершина S получает постоянную метку (0*, S *),

R = { S }, соседние с ней вершины 1, 2, 3 получают временные метки (1, S), (10, S) и (6, S) соответственно, а остальные вершины получают временные метки (¥, S) (рис.8 ).

 

 

Рис. 8

Итерация 1.

1) Минимальное значение первой части меток всех вершин равно 1 для первой вершины, т.е. arg() = 1. Метка первой вершины становится постоянной. Полагаем R:= R {1} = {S, 1}, переходим к шагу 2.

2) Просматриваем все вершины, соседние с вершиной, получившей по­стоянную метку (вершиной 1).

Для вершины 5 имеем l*(1) + l₁₅ =1 + 2 = 3 < l(5) = ¥, поэтому полагаем l(5) = 3, V(5) = 1.

Для вершины 2 имеем min(l*(1) + l₁₂, l*(S) + l₃₂ = min (1 + ¥, 10) = 10. Так как l(2) = 10, то метка вершины 2 не меняется. Переходим ко второй итерации и т.д.

Заметим, что на каждой итерации алгоритма одна очередная вершина i присоединяется к множеству R и получает постоянную метку (l*(i), v*(i)), которая в дальнейшем не меняется, а для остальных вершин j Ï R пересмат­риваются текущие значения величин l (j), некоторые из которых могут ме­няться и в дальнейшем. Результаты вычислений на начальном шаге (итерация 0) и на всех последующих итерациях удобно заносить в таблицу 2.1. Если пара чисел (l (i), v(i)) помечается символом (*), это означает, что вершина i получила постоянную метку (l*(i), v*(i)), которая в дальнейшем не меняется.

 

Таблица 2.1

Вершина итерация	0	1	2	3	4	5	6	7
s 1 2 3 4 5 6 7 t	0*, s* s 10, s 7, s ¥, s ¥, s ¥, s ¥, s ¥, s	1*, s* 10, s 7, s ¥, s 3, 1 ¥, s ¥, s ¥, s	10, s 7, s 4, 5 3*, 1* ¥, s 11, 5 13, 5	10, s 6, 4 4*, 5* ¥, s 8, 4 13, 5	7, 3 6*, 4* ¥, s 8, 4 13, 5	7*, 3* ¥, s 8, 4 13, 5	¥, s 8*, 4* 13, 5	¥, s 13*, 5*

Алгоритм закончил работу на 7-й итерации случаем, когда R = {s, 1, 2, 3, 4, 5, 7, t }, {6 } Ï R и R ¹ V, а l(6) = ¥. Это означает, что не существует пути, ведущего из вершины s в вершину 6. Для всех остальных вершин сети длины кратчайших путей найдены, а сами пути могут быть построены, как описано выше. Например, для вершины 2 имеем: (l*(2), v*(2)) = (7*, 3*); предыдущая вершина кратчайшего пути - 3. Для вершины 3 (l*(3), v*(3)) = (6*, 4*); для вершины 4 - ((l*(4), v*(4)) = (4*, 5*); для вершины 5 - ((l*(5), v*(5)) = (3*, 1*); а для вершины 1 - ((l*(1), v*(1)) = (1*, s*). Таким образом, кратчайший (s - 2) путь проходит через вершины s, 1, 5, 4, 3, 2 и его длина равна 7.

Все дуги сети, входящие в кратчайшие пути, изображены на рис.9. Пары чисел около вершин (рис.8, 9) - это найденные в результате работы алгоритма постоянные метки вершин, первая часть которых l*(i) - длина кратчайшего (s - i) пути P*(s, i), а вторая - предпоследняя вершина этого пути (последней является вершина i).

Кратчайшие пути образуют дерево, но не остовное, так как вершина 6 не соединена ни с одной другой вершиной.

 

 

Рис. 9

 

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

 

 

КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

 

Задание 8. Дана матрица расстояний между каждой парой вершин сети. Если , это означает, что в сети нет дуги, ведущей из вершины i в вершину j. Если , то вершины i и j соединены неориентированной дугой длины . Требуется по матрице L построить сеть и найти кратчайшие пути из вершины 1 во все остальные вершины сети.

 

Вариант 1	Вариант 2
Вариант 3	Вариант 4
Вариант 5	Вариант 6
Вариант 7	Вариант 8
Вариант 9	Вариант 10

 

 

ЛИТЕРАТУРА

 

1. Кузнецов А.В., Холод Н.И. Математическое программирование. – Мн., Вышэйшая школа, 1984.

2. Балашевич В.А. Математические методы в управление производством. – Мн., Вышэйшая школа, 1976.

3. Банди Б. Основы линейного программирования. – М., Радио и связь, 1988.

4. Банди Б. Методы оптимизации. Вводный курс. – М., Радио и связь, 1989.

5. Калихман И.Л. Сборник задач по математическому программированию. – М., Высшая школа, 1975.

6. ЕмеличеваЕ.В., Еровенко Л.Д., Корзников А.Д., Ласый П.Г. Сборник задач и методические указания к решению задач по математическому программированию. – Мн., ротапринт БГПА, 1996.

7. Гайков Н.Е., Емеличева Е.В., Корзников А.Д., Павлов В.В., Смирнов М.Б. Математические методы в технико-экономических задачах. – Мн., ротапринт БПИ, 1991.

 

СОДЕРЖАНИЕ

Стр.

1.	РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДОМ ЖОРДАНА-ГАУССА …………………………………………………….
	Контрольные задания для самостоятельного решения ………………..
2.	РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГЕО­МЕТРИЧЕСКИМ МЕТОДОМ …………………………………………..
	Контрольные задания для самостоятельного решения…………………
3.	Решение задачи линейного программирования Симплекс-методом…………………………………………………
	Контрольные задания для самостоятельного решения…………………
4.	ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД………………………………
	Контрольные задания для самостоятельного решения…………………
5.	ТРАНСПОРТНАЯ ЗАДАЧА……………………………………………..
	Контрольные задания для самостоятельного решения…………………
6.	Задача о максимальном потоке в сети…………………...
	Контрольные задания для самостоятельного решения…………………
7.	Сетевое планирование…………………………………………...
	Контрольные задания для самостоятельного решения…………………
8.	ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ ……………………………………..
	Контрольные задания для самостоятельного решения…………………
	ЛИТЕРАТУРА…………………………………………………………….