 |
|
АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология |
Минимальный путь в нагруженном ориентированном графеНайти минимальный путь в нагруженном ориентированном графе из вершины Рассмотрим сначала общую задачу – нахождения минимального пути из вершины vнач в vкон. Пусть D =(V, X) – нагруженный ориентированный граф, V ={ v 1,…, vn }, n >1. Введем величины Для каждого фиксированного i и k величина Положим также Составляем матрицу длин дуг C (D)=[ cij ] порядка n:
Утверждение. При i =2,…, n, k ³0 выполняется равенство
Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном ориентированном графе D из vнач в vкон. (vнач ≠ vкон)
1) Составляем таблицу 2) Если 3) Затем определяем номера i 2,…,
то есть, восстанавливаем по составленной таблице и матрице стоимости искомый минимальный путь из vнач в vкон. Пример Найдем минимальный путь из вершины v 2 в v 6 в ориентированном нагруженном графе D, изображенном на рис. 9. В рассматриваемом графе количество вершин n= 7, следовательно, матрица длин дуг ориентированного графа D будет иметь размерность 7×7.
Рис. 9.
Матрица длин дуг для рассматриваемого графа будет выглядеть следующим образом:
Согласно алгоритму, составляем таблицу стоимости минимальных путей из вершины v 2 в вершину vi не более, чем за k шагов, k =0,… n -1 (n =7, следовательно, k =0,…6). Как было определено выше,
В конечном итоге получаем следующую таблицу:
Теперь необходимо по построенной таблице и по матрице C (D) восстановить минимальный путь из вершины v 2 в v 6, который будет строиться с конца, то есть, начиная с вершины v 6. Для этого выбираем минимальное из чисел, стоящих в строке, соответствующей v 6 в таблице. Это число – 21 – длина минимального искомого пути. В первый раз такая длина была получена при количестве шагов, равном 4. В вершину v 6 мы можем попасть за один шаг из вершин v 1 и v 7 (длина соответствующих дуг 8 и 5 соответственно – данные из матрицы C (D)). Выбираем минимальную по длине из этих дуг. Далее, в вершину v 7 можно попасть из v 4 и v 5 (длина соответствующих дуг 7 и 3 соответственно). Продолжая аналогичным образом, найдем искомый путь за 4 шага минимальной длины из вершины v 2 в v 6: v 2 v 3 v 5 v 7 v 6.
Дата добавления: 2015-09-27 | Просмотры: 966 | Нарушение авторских прав |
в вершину 
по методу Форда-Беллмана.
, где i =1,…, n, k =0,1,2,…, n– 1.
.
.
. (3.1)
, то пути из vнач в vкон нет. Конец алгоритма.
то это число выражает длину любого минимального пути из vнач в vкон. Найдем минимальное k 1³1, при котором 
. По определению 
такие, что
,
,
,
.
, и 
для всех остальных вершин vi ≠ v 2, то есть первый столбец таблицы состоит из элементов, равных 
, кроме элемента 
, складываем элементы столбца 
и первого столбца матрицы стоимости и выбираем минимальное из получившихся чисел:
.