Теоретические пояснения

ОПРЕДЕЛЕНИЕ КРАТЧАЙШИХ ПУТЕЙ ПО МАТРИЧНОМУ МЕТОДУ И МЕТОДУ ФЛОЙДА

Рекомендовано для студентов специальности 220100, 220200, 220400 и других смежных специальностей

 

Составитель Крылов Ю. Д.[1]

 

Теоретические пояснения. 1

Содержание отчета. 5

Варианты заданий. 5

Контрольные вопросы.. 6

 

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

Теоретические пояснения

Распределение каналов и потоков информации на линии связи производится с учетом длины пути. Для оценки длины пути используются различные критерии: число транзитных участков между взаимодействующими узлами коммутации (УК); протяженность пути; качество тракта передачи; надежность передачи и т. д.

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

В теории потоков все методы выбора кратчайших путей основаны на утверждении о том, что если кратчайший путь mij от произвольного УКi к УКj проходит через промежуточные УК1,…, УКk (Рис. 1), то кратчайшие пути μi1,…, μkj являются частями кратчайшего пути μij от УКi к УКj.

Рис. 1

Если длина пути μi1 равна li1, то lij = li1 + l1j. Так как μij является кратчайшим, то , где N - число узлов сети. Для нахождения кратчайшего пути от узла i к узлу j необходимо просмотреть все возможные пути и выбрать тот, у которого длина наименьшая.

Имеется ряд методов определения длины кратчайшего пути. Их можно разделить на две группы: методы нумерации узлов и матричные методы.

Матричный метод определения кратчайших путей позволяет найти длины кратчайших путей между всеми узлами сети одновременно и основывается на применении операций над матрицами расстояний.

Структуру сети связи с указанием длин ветвей можно описать в виде матрицы расстояний (длин) непосредственных связей L1 = ||l1ij||, где элемент l1ij определяет длину дуги βij.

Пример. Пусть сеть связи имеет вид представленный на Рис. 2.

Рис. 2

Цифры на дугах соответствуют длинам дуг. Тогда матрица расстояний будет иметь вид

Элементы главной диагонали равны нулю, так как принимается, что расстояние внутри узла отсутствует. Если между парой узлов отсутствует дуга, то соответствующий элемент матрицы равен бесконечности (∞). Если между узлами i и j имеется дуга βij, то элемент lji также принимается равным бесконечности, например, l1AF = ∞, тогда же l1FA = 15.

При анализе сетей передачи данных длину дуги удобно трактовать как задержку, которую вносит дуга при передаче информации.

Матрица расстояний непосредственных связей неориентированной сети всегда симметрична относительно своей главной диагонали. Для ориентированной сети (как в примере) она может быть несимметричной.

Возведем матрицу L1 в квадрат L2 = L1*L1. Тогда

(1).

Можно интерпретировать умножение как последовательное соединение дуг, а сложение как параллельное соединение дуг. Произведение l1ik*l1kj соответствует двухтранзитному пути, то есть пути проходящему через две дуги сети от узла i к узлу j через узел k (Рис. 3а), а сумма, например, трех произведений l1ii*l1ij + l1ij*l1jj + l1ik*l1kj трем двухтранзитным путям (Рис. 3б).

Произведения l1ii*l1ij и l1ij*l1jj фактически соответствуют однотранзитным путям, так как длина пути (задержка) внутри УК, то есть l1ii и l1jj не принимаются во внимание.

Для подсчета длины каждого из таких N транзитных путей необходимо операцию умножения заменить операцией сложения, то есть вместо l1ik*l1kj будем иметь l1ik + l1kj.

При наличии нескольких параллельных одно и двухтранзитных путей (Рис. 3б) для определения длины кратчайшего пути между узлами следует операцию сложения заменить операцией выбора из всех длин минимальной длины одно- двухтранзитного пути, то есть вместо (1) будем иметь .

Рис. 3

Таким образом элемент l2ij матрицы L2 равен длине кратчайшего пути от УКi к УКj среди всех одно и двухтранзитных путей.

При возведении матрицы L1 в r-ю степень при использовании этих операций получим матрицу Lr = Lr-1*L1, элемент которой

будет равен длине кратчайшего пути от УКi к УКj среди всех возможных одно- двух- и т.д. до r-транзитных путей.

При наличии на сети N узлов коммутации число транзитных дуг в пути без петель не может быть больше N-1. Следовательно, может потребоваться вычисление матрицы Lr, у которой rN-1. Для конкретной сети может оказаться, что

Lr = Lr-1 (2)

при r < N-1. Так как при равенстве (2) всегда выполняется равенство Lr+1 = Lr, вычисление матрицы более высокой степени прекращается, если в процессе вычисления матриц встретится равенство (2).

Матрица Lr-1 при выполнении условия (2) называется дистанционной матрицей и обозначается D = Lr-1 = Lr = || dij ||

Таким образом, элементы дистанционной матрицы равны длинам кратчайших путей между соответствующими узлами сети связи. Матрица часто называется матрицей расстояний (длин, задержек).

Для рассматриваемого примера вычислим l2AB

l2AB = min |(l1AA + l1AB); (l1AB + l1BB); (l1AC + l1CB); (l1AD + l1DB); (l1AE + l1EB); (l1AF + l1FB)| = = min |(0 + 30); (30 + 0); (∞ + 15); (20 + 15); (∞ + ∞);(∞ + ∞)|= min|30;30;∞;35,∞,∞| = 30. Аналогично вычислим остальные элементы матрицы L2, получим

, далее .

 

А затем . Здесь L4 = L3, следовательно D = L3 .

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

Если для определения длины кратчайшего пути применяется способ нумерации узлов, то при выполнении дополнительной процедуры учитывается свойство веса УКk. Это свойство заключается в том, что на пути от УКi к УКj существует УКk, для которого выполняется равенство

dij = lik + dkj. (3)

Поэтому, если выполняется условие (3), то кратчайший путь от УКi до УКj проходит по дуге βik. Переходя к УКk, находим следующую дугу (βkm), для которой выполняется условие (3) (dkj = lkm + dmj) и которая также входит в этот кратчайший путь. Так, шаг за шагом можно определить все дуги, образующие кратчайший путь.

Исключив затем кратчайший путь из рассмотрения, подобным образом определяются и другие пути от исходящего УКi к входящему УКj. Данный метод выбора кратчайших путей от одного узла до всех остальных узлов называется методом Флойда.

При методе Флойда дополнительно к дистанционной матрице на основе матрицы длин непосредственных связей составляется так называемая матрица длин непосредственных связей Г, элементы главной диагонали которой в отличие от элементов lij равных нулю имеют значения lij = ∞,где значком ∞ обозначена бесконечность. Таким образом, матрица Г легко может быть получена по матрице L1.

Пример. Для рассматриваемого случая .

Замена элемента l1ii = 0 на l1ii = ∞ в матрице Г означает, что длина дуги (задержка) в УКi принимается бесконечно большой. Это дает возможность не рассматривать все пути проходящие через исходный узел, то есть позволяет исключить пути βii, βjj, изображенные на Рис. 3б. Полученная таким способом модернизированная матрица длин Г = || γij || умножается на дистанционную матрицу D с использованием тех же операций, что и ранее. При умножении матрицы Г на матрицу D образуется матрица кратчайших путей Δ = ГD, элементы которой используются для определения путей между всеми парами узлов в сети. Каждый элемент матрицы Δ = || δij || имеет вид

(4)

В выражении (4) min означает, что из N элементов нужно выбрать элемент, с минимальным значением; pos означает, что нужно взять позицию минимального элемента. Каждый из членов (γie + dej) ¹ ∞ в выражении (4) определяет длину пути от узла i к узлу j, если первым транзитным узлом после узла i на пути к узлу j будет узел ε Î (1,…,N). Если узел ε не является соседним узлом i, то (γie + dej) = ∞. Так как γii = ∞, член (γii + dij) будет всегда ∞. При этом элемент (gij + djj) не обязательно равен ∞. Таким образом, число членов выражения (4), не равных бесконечности, равно числу n соседних УК, то есть числу исходящих из УК ребер.

Длина кратчайшего пути от узла i к узлу j равна . Позиция элемента, который соответствует этому кратчайшему пути, соответствует номеру узла, через который проходит этот кратчайший путь. Этот номер узла заносится в качестве элемента δij в матрицу кратчайших путей Δ = || δij ||.

Рассмотрим пример расчета элементов матрицы D. Пусть сеть связи имеет вид, представленный на Рис. 2, для которой матрицы L1, D и Г приведены выше. Тогда, например, длина кратчайшего пути от вершины A к вершине E матрицы Δ согласно (4) будет равна min [(γ11 + d15); (γ12 + d25); (γ13 + d35); (g14 + d45); (γ15 + d55); (γ16 + d65)] = min [(∞ + 65); (30 + 40); (∞ + 25); (20 + 45); (∞ + 0); (∞ + 40)] = 65. Значение 65 находится в выражении на четвёртом месте, что соответствует вершине D. В матрицу Δ, заносится элемент δ15, равный D.

 

Сформировав матрицу кратчайших путей Δ, для любой вершины можно построить так называемое дерево кратчайших путей, в котором из всего множества путей от узла указаны только кратчайшие от него пути ко всем остальным узлам. Например, для графа на Рис. 2, которому сопоставлена матрица L1 непосредственных связей, дерево кратчайших путей от узла A изображено на Рис. 4.

Рис. 4 Дерево кратчайших путей от вершины А ко всем остальным вершинам

Замечание. Дерево кратчайших путей для неориентированных графов (сетей) совпадает с деревом кратчайших путей от всех узлов к рассматриваемому узлу i. Для ориентированных графов (сетей связи) такого совпадения может и не быть.