Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Контуры в ориентированных графах

Пример

Применение

Как и любой базовый алгоритм, алгоритм Флойда — Уоршелла используется очень широко и много где, начиная от поиска транзитивного замыкания графа, заканчивая генетикой и управлением проектами: транспортные и другие сети. Транспортная система города - это граф, соответственно присвоив каждому ребру некую стоимость, рассчитанную из пропускной способности и других важный параметров — можно найти по самый короткий/быстрый/дешевый путь.

 

Найдем для сети кратчайшие пути между любыми двумя узлами. Ребро (3, 5) ориентировано, поэтому не допускается движение от узла 5 к узлу 3. Все остальные ребра допускают движение в обе стороны:

Шаг 0. Начальные матрицы D0 и S0 строятся непосредственно по заданной схеме сети. Матрица D0 симметрична, за исключением пары элементов d35 и d53, где d53 равно бесконечности, поскольку невозможен переход от узла 5 к узлу 3:

Шаг 1. В матрице D0 выделены ведущие строка и столбец (k = 1). Элементы d23 и d32 матрицы D0 можно улучшить.

Таким образом, чтобы на основе матриц D0 и S0 получить матрицы D1 и S1, выполняем следующие действия.

1. Заменяем d23 на d21 + d13 = 3 + 10 = 13 и устанавливаем s23 = 1.

2. Заменяем d32 на d31 + d12 = 10 + 3 = 13 и устанавливаем s32 = 1.

Матрицы D1 и S1 имеют следующий вид:

Шаг 2. Полагаем k = 2; оператор применяем к элементам матрицы D1 и S1. В результате получаем матрицы D2 и S2:

Шаг 3. Полагаем k = 3; получаем матрицы D3 и S3:

Шаг 4. Полагаем k = 4, получаем новые матрицы D4 и S4:

Шаг 5. Полагаем k = 5, вычисления закончены.

Конечные матрицы D4 и S4 содержат всю информацию, необходимую для определения кратчайших путей между любыми двумя узлами сети. Например, кратчайшее расстояние между узлами 1 и 5 равно d15 = 12.

Для нахождения соответствующих маршрутов напомним, что сегмент маршрута (i, j) состоит из ребра (i, j) только в том случае, когда sij = j.

В противном случае узлы i и j связаны, по крайней мере, через один промежуточный узел. Например, поскольку s15 = 4 и s45 = 5, сначала кратчайший маршрут между узлами 1 и 5 будет иметь вид 1->4->5.

Но так как s14 не равно 4, узлы 1 и 4 в определенном пути не связаны одним ребром (но в исходной сети они могут быть связаны непосредственно). Далее следует определить промежуточный узел (узлы) между первым и четвертым узлами. Имеем s14 = 2 и s24 = 4, поэтому маршрут 1->4 заменяем 1->2->4. Поскольку s12 = 2 и s24 = 4, других промежуточных узлов нет.

Комбинируя определенные сегменты маршрута, окончательно получаем кратчайший путь от узла 1 до узла 5: 1->2->4->5. Длина этого пути равна 12 километрам.

 

 

Одной из важнейших задач, связанных с контурами, является задача нахождения множества всех контуров.

Количество контуров ориентированного графа может быть экспоненциально большим относительно количества вершин. Поэтому при разработке алгоритмов внимание обращается не на полную трудоемкость алгоритма, а на относительную, т.е. на трудоемкость, приходящуюся на один контур.

Рассмотрим сейчас алгоритм отыскания множества вершин, принадлежащих контуру заданной длины [Евстигнеев, 1985].

Алгоритм использует матрицу смежности A и матрицу Ak, если длина контура равна k.

Выберем некоторое i, такое, что aii(k)=1. Это означает, что вершина vi принадлежит контуру длины k. Тогда вершина vj принадлежит тому же контуру, если выполняются следующие три условия:

(a) ajj(k)=1;

(b) существует n для которого aij(n)=1, т.е. существует путь длины n из vi в vj;

(c) aji(k-n)=1, т.е. существует путь длины k-n из vj в vi.

Таким образом, для каждой вершины i графа можно построить множество вершин, каждый элемент которого принадлежит некоторому контуру длины k.

 

<== предыдущая лекция | следующая лекция ==>
Замечание. Если в графе есть циклы отрицательного веса, то формально алгоритм Флойда-Уоршелла неприменим к такому графу | Барокко и рококо
Поделиться с друзьями:


Дата добавления: 2014-01-20; Просмотров: 692; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.013 сек.