Сети передачи данных. В основу алгоритма Дейкстры положен метод "наискорейшего спуска", позволяющий на основе информация о перечне всех узлов сети

 

В основу алгоритма Дейкстры положен метод "наискорейшего спуска", позволяющий на основе информация о перечне всех узлов сети, их взаимосвязи и длине каждого из кана­лов связи найти кратчайшие пути от источника ко всем другим узлам. Рассмотрим работу данного алгоритма на примере сети, представленной на рис. 6.10. Построение кротчайших путей осуществляется поэтапно, начиная с некоторого узла ai ко всем остальным узлам. Процесс является итерационным и заканчивается после того, как будет охвачен последний узел сети. На первом этапе вычисляются длины (D^i) всех путей, ведущих из первой во все связанные с ней вершины, в нашем случае это множество вершин А ={ А₂, аз, as }, для кото­рых длины путей совпадают с длинами дуг: Li,2=2; Li,3=l; Li,5=4. На основании этих значе­ний формируем таблицу маршрутов (табл. 6.1), первый столбец которой указывает на шаг итерации, второй столбец определяет множество вершин, для которых формируются пути, а остальные столбцы указывают путь и его длину.

л

\

(^А<0

Рис. 6.10. Пример сети передачи данных.

Таблица 6.1

 

 

 

	множе-	путь
шаг	ство
ите-ра ции	вер­шин
D(l,2)	D(i,3)	D(l,4)	D(l,5)	D(i,6)
	{Ai}	Ь1Д=	L^= 1	-	Ll,5^	-
	{АЬА3}	Ь1Д= 2	Li,3= 1	(Li,3+L3,4) =4	(Li3+L3,5) =3	-
	{Ai,A3, А5}	Li^= 2	Li,3= 1	(L1)3+L3,4) =4	(L1)3+L3,5) =3	(Li3+L3,5 +L5,6)=5
	{а!,аз, А5,А2}	Ь1Д=	Li,3= 1	(Li,3+L2,4) =3	(Li,3+L3,5) =3	(Li,3+L3,5 +L5)6)=5
	{А,АЗ,	Li^=	Li,3=	(Li,3+L2,4)	(Li,3+L3,5)	(Li,3+L3,5

Глава 2. Аббёойёооба ёинфоадшб пйдйё

 

 

		А5,А2,А			=3	=3	+L5)6)=5
		4}
	6	{А.Аз,	Ь1Д=	Li,3=	(Li,3+L2,4)	(Li,3+L3,5)	(Li,3+L3,5
		А5,А2,А			=3	=3	+L5)6)=5
		4,Аб}

Среди доступных путей выбираем минимальный, в нашем случае это путь (В^з) из пер­вой в третью вершину. Далее, вычисляем пути, ведущие из вершины ai во все вершины, смежные с вершиной аз. Это осуществляется за счет добавления к величине пути (В^з) дли­ны соответствующей дуги. Полученные таким образом значения путей заносятся в таблицу маршрутов, если в какую — то из вершин путь был уже ранее определен, то фиксируется ми­нимальное значение пути. Так, например, после первого шага длина пути D^s = Li,5=4, а по­сле второго шага формируется новое значение пути di^ равное (Li,3 + Ьз,5)=3, которое и зано­сится в таблицу маршрутов. В общем случае правило обновления маршрутов определяется на основании условия:

By (minfDj,!, Bj^+Lk.m]), где By— длина маршрута из исходной в расчетную вершину, Bjjc— длина пути из исходной (j-ой) в текущую (k-ю) вершину, a L^m— длина дуги между текущей и расчетной (m-ой) вершинами. В результате третьего шага итерации формируется новый маршрут Bi,6. На последующих этапах итерации осуществляется дальнейшая коррек­тировка маршрутов до тех пор, пока не будут рассмотрены все вершины графа связей. Ана­логичным образом вычисляются маршруты и для других узлов сети передачи данных.

Алгоритм Форда — Фалкерсона также состоит из двух частей: задания начальных ус­ловий и расчетов кратчайших расстояний. По сравнению с предыдущим алгоритмом в дан­ном случае формирование маршрутов осуществляется в обратном порядке — от узла получа­теля ко всем остальным узлам. Алгоритм заканчивает свою работу, когда для всех узлов фиксируется их расстояние до узла получателя и отмечаются следующие узлы на кратчай­шем пути по направлению к получателю. В результате чего для каждого 1-го узла вычисляет­ся значение (k, By), где: k — номер следующего узла от текущей (i-ой) вершины п направле-ни]э к конечному узлу (Aj). На начальном (первом) этапе выбирается узел назначения Aj, для которого устанавливается значение Dy=0 и отмечаются (., -) все остальные узлы. На вто­ром и последующих этапах в соответствии с условием: By (тт[В^ +Lk,J) осуществляется вычисление или корректировка маршрутов для каждой i-ой вершины. Выбор минимального пути осуществляется по всем направлениям (ребрам), ведущим из вершины, для которой в данный момент рассчитывается маршрут.

Рассмотрим работу данного алгоритма на примере сети, представленной на рис. 6.10. В качестве узла назначения выбираем первый узел, D^ijN), все остальные узлы получают мет­ки (.,-). Полученные значения заносятся в таблицу маршрутов (табл. 6.2).

Таблица 6.2

 

шаг	метки
итера-	узлов
ции
	С,-)	С,-)	С,-)	С,-)	С,-)
	(1,2)	(1Д)	(2,3)	(3,3)	(5,5)
	(1>2)	(1Д)	(2,3)	(3,3)	(5,5)

На втором шаге вычисляется значение (1,2) для второго узла и значение (1,1) для третьего узла. На данном этапе для четвертого узла могут быть определены два из трех воз-