Исследование процессов маршрутизации

1. Инициализация. Т=Дерево = {s},

то есть множество исследованных вершин состоит пока что только из вершины-источника.

L(n) = w(s, п) дляп¹ s,

то есть стоимости начальных путей к соседним вершинам представляют собой просто стоимости линий связи.

2. Получить следующую вершину.

Найти следу

ющую вершину, не принадлежащую множеству T и имеющую путь от вершины s с минимальной стоимостью, и включить эту вершину во множество Tи в Дерево. Кроме того, к дереву добавляется ребро, инцидентное этой вершине и вершине множества T, входящей в путь с минимальной стоимостью. Это может быть сформулировано следующим образом. Найти вершину xÏТ такую, что

L(x) = minL(j)

jÏT

Добавить вершину х к множеству T и к дереву; добавить к дереву ребро, инцидентное вершине х, составляющее компонент пути L(x) с минимальной стоимостью, то есть последний ретрансляционный участок пути.

3. Обновить путь с минимальной стоимостью.

L(n) = min[L(n), L(x) + w(x, п)] для всех пÏ Т.

Если последняя величина минимальна, то с этого момента путь от вершины до вершины п представляет собой конкатенацию пути от вершины s до вершины х и пути от вершины х до вершины п.

Алгоритм завершает работу, когда все вершины добавлены к множеству Т. Таким образом, для работы алгоритма требуется |V| итераций. К моменту окончания работы алгоритма значение L(x), поставленное в соответствие каждой вершине x представляет собой минимальную стоимость (длину) пути от вершины s до вершины х. Кроме того, Дерево представляет собой связующее дерево исходного ориентированного графа, определяющее пути с минимальной стоимостью от вершины s до всех остальных вершин.

На каждой итерации при выполнении шагов 2 и 3 к множеству Tдобавляется одна новая вершина, а также находится путь с минимальной стоимостью вершины s до этой вершины. Другими словами, на каждой итерации к множеству добавляется вершина х, а значение L(x) на этот момент времени представляет собой минимальную стоимость пути от вершины s до вершины х. Более того, путь с минимальной стоимостью определяется уникальным путем от вершины s , вершины х во множестве Т. Этот путь проходит только по вершинам, принадлежащим множеству Т. Чтобы понять это, рассмотрим следующую цепочку рассуждений. Вершина х, добавляемая на первой итерации, должна быть смежной с вершиной и не должно существовать другого пути к вершине х с меньшей стоимостью. Если вершина х не является смежной с вершиной s, тогда должна существовать другая вершина, смежная с вершиной s, представляющая собой первый транзитный участок пути с минимальной стоимостью к вершине х. В этом случае при выборе вершины, добавляемой к множеству Т, предпочтение будет отдано этой вершине, а не вершине х. Если вершина х является смежной с вершиной s, но путь s—х не является путем с наименьшей стоимостью от вершины s до вершины х, то это значит, что существует другая смежная с вершиной sвершина у, находящаяся на пути с минимальной стоимостью, и при выборе добавляемой к множеству Т вершины предпочтение будет отдано вершине у, а не вершине х. После выполнения k итераций во множество Tвойдут k вершин и будет найден путь с минимальной стоимостью от вершины sдо каждой из этих вершин. Теперь рассмотрим все возможные пути от вершины s до вершин, не входящих в множество Т. Среди этих путей существу один путь с минимальной стоимостью, проходящий исключительно по вершинам, принадлежащим множеству Т, заканчивающийся линией, непосредственно связывающей некую вершину множества Т с вершиной, не принадлежащей множеству Т. Эта вершина добавляется к множеству Т, а соответствующий путь считается путем с наименьшей стоимостью к данной вершине.

В табл. 1 показан результат применения данного алгоритма к графу, представленному на рис.1.

 Скачать реферат