ТОП 10:

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



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

н=i0, v1, i1, v2, i2,..., vk, ik=к, соединяющих вершины t и s, где h1(vj)=ij1, h2(vj)=ij , j=1,2,3,…,k, с длиной , определить путь, длина которого минимальна.

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

путь 2 – 1, v1, 3, v7, 5, v12, 6, v14, 9.

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

 

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

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

Значение Wн будет длиной кратчайшего пути от вершины н до вершины к. Для кратчайшего пути н=i0, v1, i1, v2, i2,..., vk, ik=к справедливо равенство . Алгоритм Белмана–Калабы представляет собой аналог метода простой итерации. Начальное приближение имеет вид

Первый этап.

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

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

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

Второй этап.

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

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

Положить ,

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

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

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

дуга v1 v2 v3 v4 v5 v6 v7 v8 v9 v10
длина

 

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

 

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

  шаг 0
вершина W0
¥
¥
¥
¥
¥

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

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

  шаг 0 шаг 1
вершина W0 W1 v
¥ ¥
¥ v6
¥ ¥
¥ v9
¥ v10

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

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

  шаг 4 шаг 5
вершина W4 (W5,v)
(4,v3)
(3,v4)
(2,v7)
(2,v8)
(1,v10)
( 0, )

 

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

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

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


Алгоритм.

Первый этап.

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

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

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

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

Второй этап.

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

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

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

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

 

Таковой является v6, для нее h1(v6)=2, h2(v6)=6, поэтому полагаем W2=4+W6=4, заменяем значения в клетке 2 на (4, v6), получим

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

Следующей будет дуга v6, поэтому полагаем W1=1+W2=4, поэтому

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

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

вершина
(W,v) (4,v3) (3,v4) (2,v7) (2,v8) (1,v10 (0,)

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







Последнее изменение этой страницы: 2016-06-29; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.236.35.159 (0.01 с.)