Задача отыскания кратчайшего расстояния в сети между парами вершин

Постановка задачи. Пусть задан ориентированный граф G =á E, V, H ñ, в котором для каждой дуги v Î V задана длина с_v. На множестве вершин E выделены две вершины н и к (соответственно начало и конец пути). Требуется среди всех путей

н = i ₀, v ₁, i ₁, v ₂, i ₂, ..., v_k, i_k = к, соединяющих вершины t и s, где h ₁(v_j)= i_{j– 1}, h ₂(v_j)= i_j, j =1,2,3,…, k, с длиной , определить путь, длина которого минимальна.

На графе, изображенном на этом рисунке, выделено 2 пути из вершины 1 в вершину 9: путь 1 – 1, v ₂, 4, v ₉,7, v ₁₆, 9,

путь 2 – 1, v ₁, 3, v ₇, 5, v ₁₂, 6, v ₁₄, 9.

Если считать, что длины всех дуг равны 1, то длина первого пути равна 3, длина второго пути равна 4. Не трудно видеть, что длина кратчайшего пути равна 3, и кратчайший путь не единственный.

 

Алгоритм Беллмана – Калабы

Обозначим через W_i длину кратчайшего пути от вершины i до вершины к. Согласно принципа оптимальности Беллмана

Значение W_н будет длиной кратчайшего пути от вершины н до вершины к. Для кратчайшего пути н = i ₀, v ₁, i ₁, v ₂, i ₂, ..., v_k, i_k = к справедливо равенство . Алгоритм Белмана–Калабы представляет собой аналог метода простой итерации. Начальное приближение имеет вид

Первый этап.

0– шаг (задание начального приближения). , где M – достаточно большое число, например заведомо большее, чем длина самого длинного пути.

j – ый шаг. (j =1,2,3, ...)

Если после двух следующих друг за другом итерациях j и (j+ 1) для всех i Î E, то полагаем для всех iÎE. Если W_н ³ M, то задача не имеет решения (нет путей между вершинами н и к), в противном случае переходим к выполнению второго этапа.

Второй этап.

0– шаг. Положить .

j – ый шаг (j =1,2,3, ...)

Положить ,

Если , то алгоритм прекращает работу, в противном случае переходим к следующему шагу.

Пример. Пусть граф имеет следующий вид:

Для него длины дуг заданы в таблице:

дуга	v 1	v 2	v 3	v 4	v 5	v 6	v 7	v 8	v 9	v 10
длина

 

Эти длины также записаны на графе рядом с дугами.

 

Шаг 0. Заполнения столбца «шаг 0» очевидно.

	шаг 0
вершина	W ^0
	¥
	¥
	¥
	¥
	¥

Значения поместим в граф рядом с вершинами

Шаг 1. Заполнение клетки (6, шаг 1) очевидно. Вычислим , в клетку (1, шаг 1) вносим (¥,–). Далее вычислим , минимум достигается на дуге v ₆. И так далее, получим значения остальных клеток шага 1.

	шаг 0	шаг 1
вершина	W ^0	W ^1	v
	¥	¥	–
	¥		v 6
	¥	¥	–
	¥		v 9
	¥		v 10
			–

Жирным выделены дуги, на которыхдостигается минимум при вычислении W ¹.

Выполняя аналогичным образом 4 шага получим

	шаг 4	шаг 5
вершина	W ^4	(W ^5, v)
		(4, v 3)
		(3, v 4)
		(2, v 7)
		(2, v 8)
		(1, v 10)
		(0, –)

 

Для восстановления оптимального пути используем столбец шага 2, движение начинаем из вершины 1, для нее запомнена дуга v ₃. По этой дуге попадаем в вершину 2, из вершины 2 по дуге v ₄ в вершину 4, т.д. Таким образом, оптимальный путь следующий (1, v ₃,2, v ₄,4, v ₈,5, v ₁₀,6), его длина равна .

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

Пусть W_i – верхние оценки кратчайших расстояний от вершины i до вершины к, для самой вершины к W_к =0. Если для всех дуг v Î V выполняется , то оценки W_i дают кратчайшие расстояния от вершины i до вершины к. Заметим, что если некоторая дуга v Î V содержится в кратчайшем пути из некоторой вершины i (например из вершины h ₁(v)) в вершину s, то для нее . Если нашлась дуга v Î V, для которой ,то оценки W_i не дают кратчайшие расстояния от вершин i до вершины s так как оценку можно улучшить, положив . На этом свойстве основан алгоритм Флойда.

Алгоритм.

Первый этап.

0– шаг (задание начального приближения).

Положить для всех iÎE\ { к } W_i =¥, для i=к W_к =0;

j – ый шаг. (j =1,2,3,...)

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

Второй этап.

Если W_н < ¥, то выполняем второй этап алгоритма Беллмана–Калабы, в противном случае задача решения не имеет.

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

На графе ищем дугу, для которой ,

вершина
(W,v)	(¥, –)	(¥, –)	(¥, –)	(¥, –)	(¥, –)	(¥, –)

 

Таковой является v ₆, для нее h ₁(v ₆)=2, h ₂(v ₆)=6, поэтому полагаем W ₂=4+ W ₆=4, заменяем значения в клетке 2 на (4, v ₆), получим

вершина
(W,v)	(¥, –)	(4, v 6)	(¥, –)	(¥, –)	(¥, –)	(¥, –)

Следующей будет дуга v ₆, поэтому полагаем W ₁=1+ W ₂=4, поэтому

вершина
(W,v)	(5, v 3)	(4, v 6)	(¥, –)	(¥, –)	(¥, –)	(¥, –)

И так далее, на последнем шаге получим таблицу

вершина
(W,v)	(4, v 3)	(3, v 4)	(2, v 7)	(2, v 8)	(1, v 10	(0, –)

Восстанавливая по этой таблице путь путь, получим ранее полученное решение.