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

Рисунок. 2

V1 V3

Рисунок.3

V1 V3

Рисунок.4

V1 V3

Рисунок.5

V1 V3

Рисунок.6

V1 58 height=270 src="images/referats/3783/image025.png"> V3

Рисунок.7

V1 V3

1.3.Алгоритм Беллмана-Форда

Алгоритм Беллмана — Форда может быть сформулирован следующим образом. Требуется найти кратчайшие пути от заданной вершины при условии, что эти пути состоят максимум из одного ребра, затем найти кратчайшие пути при условии, что эти пути состоят максимум из двух ребер, и т. д. Этот алгоритм также работает поэтапно, формально он может быть определен следующим образом. Введем обозначения:

· s — вершина-источник;

· w(i,j) — стоимость линии от вершины i до вершины j, причем w(i, j) = 0 или w(i,j) = ¥, если две вершины не соединены напрямую, и w(i,j) => 0, если две вершины соединены напрямую;

· h — максимальное количество ребер в пути на текущем шаге алгоритма;

· Lh(n) — минимальная стоимость пути от вершины sдо вершины п при условии, что этот путь состоит не более чем из h ребер.

Алгоритм состоит из двух шагов. Шаг 2 повторяется до тех пор, пока стоимости путей не перестанут изменяться.

1. Инициализация:

L0(n) = ¥ для всех п ¹s,

Lh(s) = 0 для всех h.

2. Обновление. Для каждого последовательного h>= 0 и для каждого п ¹s вычислить

Lh+1(n) - min[Lh(j) + w(j, n)].

j

Соединить вершину п с предыдущей вершиной j, для которой находится минимальное значение, и удалить любое соединение вершины п с предыдущей вершиной, образованное на более ранней итерации. Путь от вершины sдо вершины п заканчивается линией связи от вершины j до вершины п.

При h = К для каждой вершины-получателя п алгоритм сравнивает потенциальный путь от вершины sдо вершины п длиной К + 1 с путем, существовавшим к концу предыдущей итерации. Если предыдущий более короткий путь обладает меньшей стоимостью, то он сохраняется. В противном случае сохраняется новый путь от вершины s до вершины п длиной К + 1. Этот путь состоит из пути длиной К от вершины К до некоей вершины j и прямого участка от вершины j до вершины п. В этом случае используемый путь от вершины s до вершины j представляет собой путь, состоящий из К ретрансляционных участков.

В табл. 2 показан результат применения этого алгоритма к графу, представленному на рис. 8, в котором в качестве вершины s выбираем: вершину V1. На каждом шаге алгоритм находит путь с минимальной стоимостью, максимальное число ретрансляционных участков в котором равно h. После последней итерации алгоритм находит путь с минимальной стоимостью к каждой вершине, а также вычисляется стоимость этого пути. Та же процедура может быть применена к вершине V2 и т. д. Результаты работы алгоритмов Дейкстры и Беллмана - Форда совпадают.

Рисунок.8

V2

V1 V3

Таблица№2

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