Матрицы маршрутов

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

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

Пример аккордной матрицы приведен на рис. 1.17.

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

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

В качестве элементов матрицы заносятся номера узлов, являющихся первыми компонентами соответствующих маршрутов к соответствующим узлам сети. При этом если первым элементом маршрута из узла в узел у и соответствующего строке, является

Рис. 1.17.

Рис. 1.18.

Пример шаговой матрицы маршрутов приведен на рис. 1.18.

Принципиально полная совокупность каждого типа матриц маршрутов позволяет построить полную совокупность матриц другого типа. В памяти центров коммутации матрицы маршрутов хранятся в виде маршрутных таблиц.