Расчет пути минимально веса в телекоммуникационной сети

Исходные данные для выполнения задания

Таблица 1.1 - Варианты заданий для раздела 2

Таблица 1.2 - Варианты заданий для раздела 3

Таблица 1.3 - Варианты заданий для раздела 3

Вариант	C, кбит/с	λ, пак./с	L, байт	, с	, c
0	64	3	400	0,25	0,325
1	64	2	300	0,25	0,325
2	64	4	450	0,25	0,325
3	64	5	500	0,25	0,325
4	64	4	550	0,25	0,325
5	64	1	400	0,25	0,325
6	128	6	500	0,2	0,25
7	128	5	300	0,2	0,25
8	128	2	400	0,2	0,25
9	128	3	550	0,2	0,25
10	128	4	350	0,2	0,25
11	256	8	600	0,1	0,15
12	256	5	300	0,1	0,15
13	256	6	400	0,1	0,15
14	256	4	350	0,1	0,15
15	256	3	500	0,1	0,15
16	96	2	350	0,25	0,325
17	96	3	400	0,25	0,325
18	96	2	750	0,25	0,325
19	96	3	200	0,25	0,325
20	96	4	900	0,25	0,325
21	192	5	900	0,2	0,25
22	192	4	950	0,2	0,25
23	192	2	1100	0,2	0,25
24	192	4	1300	0,2	0,25
25	192	3	1200	0,2	0,25
26	288	4	500	0,1	0,15
27	288	2	600	0,1	0,15
28	288	3	700	0,1	0,15
29	288	6	850	0,1	0,15
30	288	5	950	0,1	0,15

Раздел 1

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

С помощью алгоритма Беллмана-Форда можно найти кратчайшие пути между заданной вершиной и всеми остальными вершинами графа. Сложность алгоритма Беллмана-Форда составляет O (n х m), где n – число вершин, а m – число ребер графа.

Нахождение пути минимального веса в графе.

Рассмотрим сначала общую задачу – нахождения пути минимального веса во взвешенном графе из вершины v _нач в v _кон по методу Беллмана-Форда.

Пусть D=(V, X) – взвешенный ориентированный граф, V={v₁,…,v_n}, n>1, где V – множество вершин графа, а X – множество ребер графа. Введем величины , где i=1,…,n, k=0,1,2,…,n–1.

Для каждого фиксированного значения i и k величина  равна длине минимального пути среди путей из v_нач в v_i содержащих не более k ребер графа. Если путей нет, то .

Положим также, что

.

Составляем матрицу длин дуг C(D)=[c_ij] порядка n:

Для значений i= 1,…,n, k ³ 0 всегда выполняется равенство

.                   (2.1)

Математическая формулировка алгоритма Беллмана-Форда

для нахождения пути минимального веса во взвешенном графеиз v _нач в v _кон.( v _нач ≠ v _кон).

Величины  будем записывать в виде матрицы, где i - строка, а k – столбец с таким условием, что столбец  является первым столбцом этой матрицы.

1. Составляем таблицу , i=1,…,n, k=0,…,n-1. Если , то пути из v_нач в v_кон нет. Конец алгоритма.

2. Если  то это число выражает минимальный вес любого пути из v_нач в v_кон. Найдем минимальное значение k₁³1, при котором . По определению  получим, что k₁- число ребер, входящих в путь наименьшего веса среди всех возможных путей из v_нач в v_кон.

3. Затем по составленной таблице и матрице длин ребер можно найти искомый путь минимального веса из v_нач в v_кон (число ребер в этом пути мы уже получили на втором шаге – это k₁). Проще всего найти искомый путь, двигаясь по графу в обратном направлении по ребрам с наименьшим весом, т.е. от вершины v_кон к вершине v_нач. Единственное, что следует учесть – на последнем шаге должно быть выбрано ребро, которое ведет в начальную вершину графа - v_нач.

Расчет пути минимально веса в телекоммуникационной сети

 Найдем путь минимального веса из вершины v₁ в v₄ в графе G, изображенном на рисунке 1.1. В рассматриваемом графе количество вершин n=7, следовательно, матрица длин ребер графа G будет иметь размерность 7 × 7.

Рисунок 2.1 – Граф G (Вариант 0)

Матрица длин ребер для рассматриваемого графа будет выглядеть следующим образом:

.

Согласно алгоритму, составляем таблицу минимальных путей из вершины v₁ в вершину v_i не более, чем за k шагов, k=0,…n-1 (n=7, следовательно, k=0,…6). Как было определено выше, , и  для всех остальных вершин v_i ≠ v₁, то есть первый столбец таблицы состоит из элементов, равных , кроме элемента  (так как начальной вершиной является v₁). Второй столбец таблицы будет повторять первую строку матрицы длин ребер, поскольку представляет собой длину возможных путей из вершины v₁ за один шаг. Кроме того, все элементы строки таблицы, соответствующей начальной вершине (i-й строки) следует положить равными нулю (для рассматриваемого примера все элементы первой строки должны быть нулевыми, так как начальной вершиной является v₁).

Далее по формуле (1.1) находим по столбцам все оставшиеся элементы таблицы. Например, чтобы найти элемент , складываем элементы второго столбца таблицы -  и второго столбца матрицы стоимости и выбираем минимальное из получившихся чисел:

.

и, продолжая далее:

В конечном итоге получаем следующую таблицу:

Теперь необходимо по построенной таблице и по матрице C(G) нужно восстановить путь минимального веса из вершины v₁ в v₄, который будет строиться с конца, то есть, начиная с вершины v₄. Для этого выбираем минимальное из чисел, стоящих в строке, соответствующей v₄ в таблице. Это число – 18 – вес искомого пути минимального веса. В первый раз такая длина была получена при количестве шагов, равном 3. В вершину v₄ мы можем попасть за один шаг из вершин v₃, v₅ и v₇ (длины соответствующих ребер равны 6, 9 и 17 соответственно – данные из матрицы C(G)). Выбираем из этих ребер ребро с минимальным весом, т.е ребро с весом 6, соединяющее вершины v₃ и v₄. Далее, в вершину v₃ можно попасть из v₂, v₅ и v₇ (длины соответствующих ребер 12, 1 и 6 соответственно). Продолжая аналогичным образом, найдем искомый путь минимального веса за 3 шага из вершины v₁ в v₄: v₄ v₃ v₅ v₁ (v₁ → v₅ → v₃ → v₄). Вес искомого пути равен сумме весов всех ребер, входящих в этот путь: 11+1+6=18.