КАТЕГОРИИ: Архитектура-(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) |
Алгоритмы поиска кратчайших путей Дейкстры и ФлойдаПоиск путей на графе в ширину
При поиске в глубину короткие по числу звеньев пути могут находиться далеко не в первую очередь. Так самым коротким в рассмотренном примере является прямой путь из 1 в 4, но этот путь находится последним. Поиск в ширину заключается в том, что пути просматриваются по возрастанию числа дуг. Это соответствует проходу описанного дерева по уровням. В приведенном примере пути будут найдены в порядке · 1,4; · 1,3,4; · 1,3,2,4; · 1,3,2,5,4. Поиск в ширину реализуется сложнее. Требуется помнить не один текущий путь, а все пути, способные привести к цели. Это можно обеспечить с помощью дерева, строящегося по уровням.
Обычно в практических задачах длина пути измеряется не числом дуг, а их суммарной длиной. Термин длина носит обобщенный смысл. Синонимами этого термина являются расстояние, вес, стоимость дуг, причем могут рассматриваться и отрицательные значения. Рассмотрим два алгоритма поиска кратчайших путей между вершинами: Дейкстры и Флойда. Будем считать, что длина дуги из вершины Vi в вершину Vj задана элементом матрицы aij, причем aii=0 и aij =¥, если дуга из вершины Vi в вершину Vj отсутствует. В алгоритме Дейкстры находится кратчайший путь из вершины S в вершину T. Вершинам присваиваются временные и окончательные метки, которые будем обозначать соответственно буквами C и D с индексами вершин. 1. Вершине S присваивается окончательная метка 0, то есть Cs:=0, временным меткам остальных вершин – значение ¥. 2. Пусть i – номер последней вершины, которой присвоена окончательная метка Ci. Каждой вершине j, имеющей временную метку Dj, присваивается новая временная метка по правилу Dj:=min(Ci+aij, Dj). Если значение Dj меняется, то вместе с ним сохраняется номер предыдущей вершины i. 3. Наименьшая из временных меток объявляется окончательной. Пусть k – номер этой вершины. Следовательно, Ck:=Dk. 4. Если новой окончательной метки не появилось, то пути из S в T нет. 5. Если вершина T не получила окончательной метки, то i:=k и переход к 2. 6. Конец. Полученная для вершины T окончательная метка дает величину кратчайшего пути. Сам путь восстанавливается от конца к началу и состоит из вершин, обеспечивших окончательные метки. Пусть имеется следующий граф.
3 2
Требуется найти кратчайший путь из вершины A в вершину C. Этапы расстановки меток удобно представить в виде таблицы. Окончательную метку будем отмечать жирным шрифтом и подчеркиванием. В скобках указывается предыдущая вершина.
Итак, длина кратчайшего пути равна 3. Окончательная метка 3 для вершины C получена из предыдущей вершины D. В свою очередь окончательная метка 2 для вершины D получена из вершины A. Следовательно, кратчайший путь составляют вершины A, D, C. Значения окончательных меток появляются по возрастанию, то есть алгоритм Дейкстры обеспечивает поиск в ширину. Алгоритм не работоспособен при наличии отрицательных расстояний, что иллюстрирует следующий простой пример
-3 1
Здесь кратчайший путь из A в C проходит через вершину B и равен -1, тогда как по алгоритму Дейкстры вершина C сразу получит окончательную метку 1. Трудоемкость алгоритма Дейкстры пропорциональна величине N 2, где N – количество вершин графа. Алгоритм Флойда определяет кратчайшие пути между всеми парами вершин. Снова будем считать, что длина дуги из вершины Vi в вершину Vj задана элементом матрицы aij, причем aii=0 и aij =¥, если дуга из вершины Vi в вершину Vj отсутствует. Пусть элемент aij(k) матрицы A(k) равен длине кратчайшего пути из вершины Vi в вершину Vj, с номерами промежуточных вершин, не превосходящими k. Тогда выполняется рекуррентное соотношение (*) Действительно, кратчайший путь из Vi в Vj с номерами промежуточных вершин, не превосходящими k+1, может не проходить через вершину Vk+1. В противном случае он представляет собой кратчайший путь из Vi в Vk+1 , а затем из Vk+1 в Vj. В качестве A(0) выбирается исходная матрица A. Матрица A(n) даст длины кратчайших путей между всеми парами вершин без каких-либо ограничений на промежуточные вершины. Значение aij(n) = ¥ означает отсутствие пути из вершины Vi в вершину Vj. Параллельно с описанными матрицами строится последовательность матриц B(i) для нахождения самих кратчайших путей. Элемент bij(k) матрицы B(k) устанавливается равным номеру второй вершины на кратчайшем пути из Vi в Vj с номерами промежуточных вершин, не превосходящими k, и 0 в случае отсутствия путей. Элемент bij(k+1) не меняется, если в формуле (*) минимум достигается на первом значении, и полагается равным bik+1(k), если минимально второе выражение, так как в этом случае кратчайший путь проходит через вершину Vk+1. Первоначально bij(0) матрицы B(0) полагается равным j, если есть дуга из Vi в Vj, и 0, если такая дуга отсутствует. Матрица B(n) позволяет восстановить кратчайший путь между любыми двумя вершинами. Действительно, если s=bij(n) дает вторую вершину на кратчайшем пути из Vi в Vj, то t=bsj(n) даст третью вершину, w=btj(n) - четвертую и так далее до попадания в вершину Vj. Значение bij(n) =0 означает отсутствие пути из вершины Vi в вершину Vj. Рассмотрим в качестве примера следующий граф, в котором вершины идентифицированы номерами 3
1
Для него матрицы A(0) и B(0) имеют соответственно вид
На первом шаге допускаются пути, проходящие через вершину 1. Поскольку появляется путь 4-2-1, изменения затронут вторые элементы четвертой строки, то есть матрицы A(1) и B(1) примут вид
На втором шаге допускаются пути, проходящие через вершины 1 и 2. Добавляются пути 1-2-3 и 4-1-2-3. Последний путь имеет большую длину, чем имеющаяся дуга 4-3, поэтому матрицы A(2) и B(2) примут вид
и так далее. Кратчайшие пути между всеми парами вершин будут представлены следующими матрицами A(4) и B(4)
Дата добавления: 2014-01-11; Просмотров: 945; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |