В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 105
Текст из файла (страница 105)
3. Обновление множества 5. Вершины, образующие множество 5, заменя!отса дочерними вершинами из дерева. Затем возвращаемся к шагу 2. Результатом работы этого алгоритма является связующее дерево с корнем в вершине )г!. Побочный эффект алгоритма поиска в гпирину заклкгчается в том, что он находит расстояние с кратчайшим путем от данной вершины до всех осталь- ных вершин. Расстояние с кратчайшиз! путем (5)!ог(е51-рас)г гйзтапсе) 6(з, и) меж ду вершинами 5 и и представляет собой минимальное количество ребер в любом пути от 5 до м Формальное доказательство этого утверждения довольн дл о нинов, 460 Глава 14.
Теория графов и поиск путей с минимальной стоимостью 14.2. Поиск кратчайшего пути 461 и интересующийся читатель может найти его в 160] (полное доказат ательство зани- мает три болыпих страницы). Но интуитивно понятный аргумент сф мент сформулировать нетрудно. Начнем с вершины гтрафа С и построим при помощи и алгоритма поисгс в ширину связующее дерево. Все вершины, смежные с вершин й; иой г; становятся,ц, стью дерева па уровне 1. Ясно, что вершины этой части дерева облада о лада юг свойство заключающимся в том, что дерево опрелеляет кратчайший путь от к ь от каждои верши- ны уровня 1 до вершины г.
(корня дерева). Теперь рассмотрилг в ш ер ину х на уров- не 2 дерева. В дереве вершинах связана с вершиной гпутем длин г 2. М ины . ожетлив графе С существовать более короткий путь от корня дерева до ве е ало вершиных? Нет так как зто бы значило, что в графе С существует путь длины 1 от длины от вершины х до вершины г, то есть то, что эти вергпины смежные. Теперь зададим противоположный вопрос. В дереве на расстоя 2 стоянии от верши ны г.располагаются только вершины уровня 2. Возможно ли, по в г фе С о ли, по в графе С суще- ствует некоторая вершина у, расположенная на уровне дерева с н м бо о ерем лее2, но для которой существует путь до корня дерева (вершины г) длины 1 или 2? Дру- гими словами, не пропустили ли мы какую-либо вершину графа к - фо мирования уровня 2 в дереве? Опять мы получим отрицательный ответ.
Если бы в графе С существовал путь длиной 1 от вершины г до вершины у, тогда вершина у ыла ы смежной с вершиной г и потому была бы включена в уровень 1. Если бы ино, тогда вершина у в графе С существовал от вершины гдо вершины у путь длиной 2, была бы смежной с вершиной первого уровня дерева и, следовательно, была бы включена в уровень 2. Используя такую цепочку рассуждений, можно показать, что в общем случае на любом овне г в е ур д рево включаются все вершины, которые находятся на расстоянии г от корня дерева.
Произведем оценку времени работы алгоритма поиска в ширину. После ини- циализации каждая вершина помещается в множество 5 ровно один раз, а следо- вательно, и удаляется из множества кровно один раз. Таким образом, суммарное время, затрачиваемое нь операции с множеством 5, пропорционально количеству вершин Щ (порядку графа). При обработке вершины перебираются все ее смеж- ные вершины, то есть все ее е р, . ь все ее ребра.
Ребро, ведущее к вершине, уже ггринадлегггагцей дереву, отбрасывается алгоритмом. В противном случае алгоритм должен решить, создается ли при вюпочении ребра цикл. Таким образом, основная обработка каж- дого ребра производится только один раз, поэтому суммарное время обработки ребер пропорционально числу ребер Д (размеру графа). Итак, мы можем заклю- чить, что в емя абот р р ы алгоритма поиска в ширину линейно зависит от количе- ства вершин Щ н числа ребер )Е~.
14.2. Поиск кратчайшего пути Сеть с коммутациеи пакетов (или сеть ретрансляции кадров, или сеть АТМ) можно рассматривать как ориентированный граф, в котором каждая вершина соответствует узлу коммутации пакетов, а линии связи между узлами соответствует пара параллельных ребер, по каждому из которых данные передаются в одном направлении. В такой сети ля пе д редачи пакета от узла-источника узлу-получателю по ( разным линиям через несколько коммутаторов пакетов требуется принять решение о выборе мзрагрута.
Эта задача эквивалентна поиску пути в графе. Для объединенной сети, такой как Интернет или интранет, представление ее в виде ориентированного графа также является приемлемым. В этолг случае каждой вершине соответствует маршрутизатор. Если два маршрутизатора напрямую присоединены к одной и той же локальной или глобальной сети, тогда это двустороннее соединение соответствует паре параллельных ребер, соединяющих соответствующие вершины. Если к сети напрямую присоединены более двух маршрутизаторов, тогда эта сеть представляется в виде множества пар параллельных ребер, каждая из которых соединяет два маршрутизатора. В объединенной сети для передачи 1Р-дейтаграммы от маршрутизатора-источника к маршрутизатору-приемнику по разным линиям через разные сети и маршрутизаторы пакетов требуется принять решение о выборе маршрута Эта задача также эквивалентна поиску пути в графе.
Практически во всех сетях с коммутацией пакетов и во всех объединенных сетях решение о выборе маршрута принимается на основе олной из разновидностей критерия минимальной стоимости. Если выбирается маршрут с минилгальным количеством ретрансляционных участков (хопов), тогда кзждолгу ребру. соответствующему ретрансляционному участку, назначается единичный вес. Эта задача соответствует поиску кратчайшего пути в обычном (не взвешенном) графе Но чаше всего каждому ретрансляционному участку в соответствие ставится определенная величина, называемая стоимостью (созг) передачи. Эта величина может быть обратно пропорциональной пропускной способности линии, прямо пропорциональной текущей нагрузке на эту линию пли представлять собой некую комбинацию подобных параметров.
Прп расчете стоимости могут учитываться также такие критерии, как финансовая стоимость использования ре грансляггггонного участка. В любом случае, стоимости использования ретрансляционных участков являются входными данными для алгоритма поиска пути с минимальной стоимостью, который может быть сформулирован следующим образом, Пусть имеется сеть, состоящая из узлов, соединенных двунаправленными линиями связи, и каждой линии поставлена в соответствие стоимость пересылки данных в каждом направлении. Стогглгость пути между двумя узлами опрелеляется как сумма стоимостей всех линий, входящих в данный путь.
Задача состоит в тюлг. чтобы найти путь с наименыпей стоимостью для каждой пары уююв. Обратите внимание на то, что стоимость использования ретрансляционного участка может быть разной в разных направлениях. Например, это справедливо в случае, если стоимость использования ретрансляционного участка пропорциональна длине очереди дейтаграмм, ждущих передачи.
В теории графов задаче нахождения пути с наименьшей стоимостью соответствует задача поиска ггуги с наименьшей длиной во взвешенном ориентированном графе. Болыпинство алгоритмов поиска маршрута с наименьшей стоимостью, применяющихся в сетях с коммутацией пакетов и объединенных сетях, представляют собой вариации одного из двух общих алгоритмов, известных как алгоритм Дейкстры (Пг))счгга) и алгоритм Беллмана — Форда (Вейшап — Ротс)). В этом разделе обсуждаются оба алгоритма. 462 Глава 14. Теория графов и поиск путей с минимальной стоимостью 14.2.
Поиск кратчайшего пути 463 Алгоритм Дейкстры Алгоритм Дейкстры (7 Ц может быть сформулирован следующим образом. Алга находит кратчайшие пути от даииои вершины-источника до всех осталь Разам ритм тьиых вершш перебирая пути в порядке увеличения их длин. Работа алгоритма проходит дит поэтапно, К и-му шагу алгоритм находит и кратчайших (с наименьшей стоимостью) ю) путей к /г вершинам, ближайшим к вершине-источнику. Эти вершины образ разуют мио>ке- ство Т. На шаге (й + 1) к множеству Тдобавляется вершина, ближайшая к "шая к вершине- источнику среди вершин, ие входящих во множество Т. При добавлен д влеипи каждан новой вершины к множеству Топределяется путь к ией от источника.
ф ормальио этот алгоритм может быть определен следующим образом. Введем обозначения; + Аг — множество вершин сети; + в — вершииа-источник; + Т вЂ” множество вершин, уже обработанных алгоритмом; + Дерево — связующее дерево для вершин, принадлежащих множеству Т, в ключая ребра, входя гцие в пути с паимеиьн>ей стоимостью от вершины з до каждой вершины множества Т; + гв(г, >) — стоимость линии от вершины > до вершины) причем т(Е г) = () или и>(Е >) =, если две вершины ие соединены напрямую, и и>(Е г) > О, если две вершины соединены напрямую; + Ег (п) — минимальная стоимость пути от вершины з до вершины и, известного иа данный момент алгоритму (по завершении работы алгоритма это минимальная стоимость пути от вершииы з до вершины п). Алгоритм состоит из трех шагов.
Шаги 2 и 3 повторяются до тех пор, пока множество Тие совпадет с множеством Аг. Это значит, что шаги 2 и 3 повторяются, пока для всех вершин сети ие будут найдены окончательные пути. 1. Инициализация. Т= Дерево = (з), то есть множество исследованных вершин состоит пока что только из вершины-источника.
Цп) =го(5, и) для пауз, то есть стоимости начальных путей к соседним вершинам представляют собой просто стоимости линий связи. 2. Иол итьел д алучить слвдуюгцу>о вершину. Наити следующую вершину, ие прииадлежащую множеству Т и имеющую путь от вершины з с мииимальиой стоимостью, и включить эту вершииу во множество Ти в Дерево. Кроме того, к дереву добавляется ребро, иицидеитиое этой вершине и вершине множества Т входшцей в путь с минимальной стоимостью. Это может быть сформулировано следующим образом. Найти вершину х и Т такую, что Е(х) = ппп Е( >). Добавить вершину х к множеству Т и к дереву; добавить к дереву ребро, ии- цидеитиое вершине х, составляющее компонент пути Е(х) с минимальной стоимостью, то есть последний ретрансляционный участок пути.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
