Составители:
Рубрика:
4
Учебноисследовательская лабораторная работа № 1
ОПРЕДЕЛЕНИЕ КРАТЧАЙШИХ ПУТЕЙ
ПО МАТРИЧНОМУ МЕТОДУ И МЕТОДУ ФЛОЙДА
Описание работы
Цель работы: ознакомление с методами определения кратчайших
путей в территориально-распределенных вычислительных сетях.
Распределение каналов и потоков информации на линии связи про-
изводится с учетом длины пути. Для оценки длины пути используют-
ся различные критерии [1,2,4]:
– число транзитных участков между взаимодействующими узлами
коммутации (УК);
– протяженность пути;
– качество тракта передачи;
– надежность передачи и т. д.
Кратчайшим путем передачи информации называется путь, для
которого критерий длины пути имеет наименьшее значение по сравне-
нию с его значением для других возможных путей.
В теории потоков все методы выбора кратчайших путей основаны
на утверждении о том, что если кратчайший путь m
ij
от произвольного
УК
i
к УК
j
проходит через промежуточные УК
i1
,…,УК
ik
(рис. 1), то крат-
чайшие пути m
i1,j
,…,m
ik,j
от УК
i1
,…, УК
ik
к УК
j
, соответственно, явля-
ются частями кратчайшего пути m
i,j
от УК
i
к УК
j
.
Если длина пути m
i1,j
равна L
i1,j
,то
L
i,j
= L
i,i1
+ L
i1,j
.
l
i1,j
l
i
,j
l
ik,j
OE
j
OE
ik
OE
i1
OE
i
Рис. 1
Так как m
i,j
является кратчайшим, то
,,,
1,
(),
min
jj
iiN
LlL12
(1)
Страницы
- « первая
- ‹ предыдущая
- …
- 2
- 3
- 4
- 5
- 6
- …
- следующая ›
- последняя »
