В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 106
Текст из файла (страница 106)
3. Обновить путь с ми>гимальной стоимостью. Цп) = ппп1 Цп), Е(х) + т(х, п)] для всех и и 7'. Если последняя величина минимальна, то с этого момента путь от зерпшиы в до вершины п представляет собой конкатенацию пути от вершины в до вершины х и пути от вершииыхдо вершины и, Алгоритм завершает работу, когда все верпшиы добавлены к множеству Т. Таким образом, для работы алгоритма требуется Щ итераций.
К моменту окончания работы алгоритма значение Цх), поставленное э соответствие каждой вершине х, представляет собой минимальную стоимость (длииу) пути от вершины з до вершины х. К(юмс того, Дерево представляет собой связующее дерево исходиоп> ориеитироваииого графа, определяющее пути с мипималъиой стоимостью от вер>пиш,> з до всех остальных вершин. На каждой итерации при выполнении шагов 2 и 3 к множеству Тдобавляется одна новая вершина, а также находится путь с мииимальиой стоимостью от вершины з до этой вершины. Другими словами, иа каждой итерации к множеству Т добавляется вершинах, а зиачеиие Е(х) на этот момент времени представляет собой минимальную стоимость пути от вершины з до вершины х. Более того, путь с мииимальиой стоимостью определяется уникальным путем от вершины з да вершины хво множестве Т.
Этот путь проходит только по вершинам, прииаллежащим множеству Т. Чтобы понять это, рассмотрим следующую цепочку рассужлеиий. Верпшиа х, добав.ляемая иа первой итерации, должна быть смежной с вершиной в, и ие должна существовать другого пути к вершиие х с меныпей стоимостью. Если вершина х не является смежной с вершиной к тогда должна существовать другая вершина, смсжиая с вершиной в, представляющая собой первый транзитный участок нуги с минимальной стоимостью к вершине х.
В этом случае при выборе вершины, добавляемой к множеству Т, предпочтение будет отдано втой вершине, а ие вершине х. Если вершинах является смежной с вершиной з, ио путь з — хне является путем с иаимеиыпей стоимостью от вершины з до вершииь> х, то это значит, что существует другая сме>киая с вершиной з вершина у, находящаяся иа пути с минимальной стоимостью, и при выборе добавляемой к множеству Т вершины предпочтение будет отдано вершине у, а ие вершине х. После выполнения и итераций во множество Т войдуг й вершин и будет найден путь с минимальной стоимостью от вершины в до каждой из этих вершин. Теперь рассмотрим все возможные пути от вершины з до вершин, ие входящих в миожество Т.
Среди этих путей существует один путь с минимальной стоимостью, проходящий исключительно по вершинам, прииадлежащим множеству Т (см. задание 9), заканчивающийся линией, непосредственно связывающей некую вершину множества Тс вершиной, ие принадлежащей множеству Т. Эта вершина добавляется к множеству Т, а соответствующий путь считается путем с наименьшей стоимостью к данной вершине. В табл. 14.2 и иа рис.
14.6 показан результат применения данного алгоритма к графу, представленному иа рис. 14.2, а. В даииоь> случае в качестве вершины з выбирается вершшы рь Затененные ребра показывают связуюгцее дерево для этого графа. Значения в каждой окружности представляют собой текущие оценки величины Е(х) для каждой вершины х. Вершина затеияется при добавлении к множеству Т. Обратите внимание иа то, что иа каждом шаге генерируется путь до кюкдой вер шины и вычисляется суммарная стоимость этого пути. После последней итерации 14.2.
Поиск кратчайшего пути 466 Итера- Т ЦИЯ 1 — 2 5 1 — 3 1 1 — 4 (1) 2 (1, 4) 2 (1, 2, 4) 2 (1. 2. 4, 5) 2 (1, 2, 3, 4, 5) 2 (1, 2, 3, 4, 5, 5) 2 1 — 2 4 1 — 4 — 3 1 — 2 4 1 — 4 — 3 1 1 — 4 2 1 1 — 4 2 1 1 — 4 2 1 1 — 4 2 14 — 5 1 — 4 — 5 1 — 2 3 1 — 4-5 — 3 1 — 2 3 1 — 4 — 5 — 3 1 — 4 — 5 4 1 — 4 — 5 4 1 — 4 — 5 4 1 — 4 — 5 — 5 1 — 4 — 5 — 5 1 — 4 — 5 — 5 1 — 231 — 4 — 5-311 — 42 У5 Т= (1) Т= (1,4) Еьм(п) — ппп[Ег(!) + и() л)]. У4 1 Уь Т = (1, 2, 4) У5 Т = (1, 2, 4, 5) У5 У5 У4 Т = (1, 2, 3, 4, 5) Т= [1, 2, 3, 4, 5, 5) 464 Глава 14.
Теория графов и поиск путей с минимальной стоимостью находится путь с минимальной стоимостью до каждой вершины и выч!гсляегся с»ь тата ° утн.тажепр целя м к тбь1 римене аквер ! е1/2 т.д. Таблица 14.2. Пример работы алгоритма выбора маршрута с минимальной стоимостью по Дейкстре (з = 1) для графа, показанного на рис. 14.2 1.(2) Путь Ь(3) Путь Ц4) Пугь 1.(5) Путь Е(5) Пу! Рис. 14.5.
Применение алгоРитма Дейкстры к графу, представленному на рнс. 14.2 Модно показать [60) „что время работы алгоритма Дейкстры пропорционально [ у1Е ![тобы почувствовать это интуитивно, обратите внимание на то, что алгоритм выполняет [У[ — 1 итерацию, а количество операций, выполняемых на каждой итерации, пропорционально ['г1!. Алгоритм Беллмана — Форда Алгоритм Веллмана — Форда [86[ может быть сформулирован следующим образо!, требуется найти кратчайшие пути от ааданной вершины при условии, что эти пути состоят максимум из одного ребра, затем найти кратчайпше пути при условии, по ли пути состоят максимум из двух ребер, и т.д.
Этот алгоритм также работает поэтапно. Формалыю он может быть определен следующим образом. Введем обозначения: + з — вершина-источник; + га(Е)) — стоимосты!инин от вершины ! до вершины 1, причем ш(Е !) = О или га(Е у) =, если две вершины не соединены напрямую, н ю(!',Я > О, если две вершины соединены напрямую; + л —. максимальное количество ребер в пути на текущем шаге алгоритма; + Ел(п) — минимальная стоимость пути от вершины здо вершины н при условии, что этот путь состоит не более чем нз л ребер. Алгоритм состоит двух шагов. Шаг 2 повторяется до тех пор, пока стоимости путей не перестанут изменяться. 1. Инио,иализация; Ео(п) = для всех и и з, Ек(з) = О для всех Ь.
2. Обновление, Для каждого последовательного л > 0 и для каждого и и з вычислить Соединить вершину и с предыдущей вергпиной7, для которой находится минимальное значение, и удалить любое соединение вершины и с предыдущей вершиной, образованное на более ранней итерации. Путь от верн!ины з до вершины и заканчивается линией связи от вершины) до верн!ины п. Прил = К для каждой вершины-получателя п алгоритм сравнивает потенциальный путь от пер!инны з до вершины п длиной К+ 1 с путем, существовавшим к концу предыдущей итерации. Если предыдущий более короткий путь обладает мсныпей стоимостью, то он сохраняется.
В противном случае сохраняето! новый путь от вершины з до вершины п длиной К+ 1. Этот путь состоит из пути длиной Кот вершины з до некоей вершнньц и прямого участка от вершины) до вершины и. В этом случае используемый путь от вершины з до вершины 7 представляет собой путь, состошций из К ретрансляционных участков, найденный на предыдущей итерации (см. задание 10). По завершении работы алгоритма вычисляется связуюгцее дерево графа. В табл.
14.3 и на рис. 14.7 показан результат применения этого алгоритма к графу, представленному па рис. 14.2, а, в котором в качестве вершины з выбирается вершина Ун На каждом шаге алгоритм находит путь с минимальной стоимостью, максимальное число ретрансляционных участков в котором равно Ь. После послед- 14.4. Задания 467 Ь ьл[2) Путь ьь13) Путь Гь(4) Пуп ).ь(5) Путь Гь(6) Г!уть О 1 2 1 — 2 2 2 1 — 2 3 2 1 — 2 4 2 ! — 2 1 ! — 4 1 1 — 4 2 1 — 4 — 5 !О 1 1-4 2 1-4 — 5 4 ! ! — 4 2 ! — 4 — 5 4 1 — 3 1 — 4 — 3 1 — 4 — 5 — 3 1 — 4 — 5 — 3 1 — 3-6 1 — 4-5-6 1 — 4 — 5 — 6 ув Л=з 14.4.
Задания $66 Глава 14. Теория графов и поиск путей а минимальной стоимостью ней итерации алгоритм находит путь с минимальной стоимостью к каждой ве шине, а также вычисляется стоимость этого пути. Та же процедура может бь!ть пРименена к веРшине Ут и т. д. ОбРатите внимание на то, что РезУльтаты Рабаты алгоритмов Дейкстры и Беллмана — Форда совпадают, Таблица 14.3. Пример работы алгоритма выбора маршрута с минимальной сто имостью по Белпману — Форду !в = 1) для графа, показанного на рис. 14.2 Рис. 14.7. Применение алгоритма Беллмена — Форда к графу, представленному на рис. 14.2 Можно показать [60], что время рабаты алгоритма Беллмена — Форда пропорционально Щ х Щ.
Чтобы почувствовать это интуитивно, обратите внимание на то, что алгоритм выполняет ٠— 1 итерацию, а каждая итерация включает определение веса каждого ребра. Сравнение алгоритмов Интересно сравнить эти два алгоритма в плане информации, собираемой ими. Рас- смотрим сначала алгоритм Белль!ана — Форда. При рассмотрении вершины и тре- бустся знание стоимости использования линий, связывающей рассматриваемую вершину со ершину со всеми соседними вершинами, то есть е(Ь и), а также суммарную стоимость пути к каждой из этих вершин от вершины-источника з, то есть 1ь(О. Каждая вершина может ина может хранить информацию о путях к другим вершинам сети и стоимости этих путей, а также время от времени обмениваться этой информацией со своими нспосредс посредственными соседями. Таким образом, для обновления данных а пугях и их стоимо х стоимостях каждая вершина можсг применять формулу из шага 2 алгоритма Беллмаиа — Форда, испачьзуя информацию, полученную от своих соседей, и сведения о ста ения о стоимости линий связи.
С другой стороны, рассмотрим алгоритм Дейкстры. а шаге ы. На шаге 3 каждая вершина должна обладать полной информацией о топологии сети. Это значит, что каждая вершина должна знать стоимость всех линий в сети, В общем, для сравнения достоинств обоих алгоритмов следует учесть время ра о аботы каждого алгоритма и объем информации, которую потребуется собрать у других зл ругих узлов обычной или объединенной сети. Также значение имеет выбранный вариант реализации алгоритма. И последнее. Известно, чта оба алгоритма приводят к одному и тому же результ ту при агу при условии неизменности топологии и стоимости линий, Если стоимость лини ме иний меняется со временем, алгоритм попытается приноровиться к этим изменениям. Но если стоимость линий зависит от графика, который, в свою очередь, зависит от выбираемых маршрутов, тогда возникает обратная связь, которая может привести к неустойчивой работе алгоритма.
14.3. Рекомендуемая литература Превосходное элементарное введение в теорию графов можно найти в [170] [ 0]и[45] В обеих книгах содержатся многочисленные задачи и решения, что делает их пригодными для самостоятельного изучения. Более полное описание теории графов с детальным анализом связую!цих деревьев и алгоритмов поиска кратчайшего пути содержится в [105]. В [60] имеется детальное описание алгоритмов перебора графов, включая детальный анализ алгоритмов поиска кратчайших путей, обсуждавшихся в данной главе. В [28] также подробно обсуждаются эти алгоритмы. 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
