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