Матричный способ задания сетей

Матричное представление структуры сети дает более удобный способ описания, чем графическое, особенно при большом числе вершин и дуг. Взаимосвязь между вершинами сети можно определить при помощи матрицы смежности вершин графа. Это квадратная матрица n-го порядка, строки и столбцы которой соответствуют вершинам графа. Элементы матрицы равны 1, если существует дуга (i, j) и 0 – в противном случае. Например,матрицы смежности вершин графа, изображенного на рис. 6. 1 имеет вид

№ вершины

Для неориентированной сети матрица является симметричной. Количественные характеристики дуг сети. а также взаимосвязь между ее вершинами могут быть представлены с помощью матрицы весовых коэффициентов, которая задается массивом ( – количественный параметр, обычно называемый длиной дуги (i, j), ). Для неориентированной сети матрица является симметричной.

Задача о кратчайшем пути

Одной из наиболее важных оптимизационных задач на сети является задача нахождения цепи, соединяющей два узла – исходный узел S и узел назначения Т, которая имеет минимальную возможную длину. Алгоритм нахождения кратчайшего пути для сетей без циклов предложен Дейкстрой в 1959г. и считается одним из наиболее эффективных. Он основан на приписывании узлам либо временных, либо постоянных пометок и имеет рекурсивный характер. Все вычисления выполняются с использованием информации об уже определенных на предшествующих шагах кратчайших расстояниях.

Для заданного узла j через обозначим оценку длины кратчайшей цепи из исходного узла S в этот узел. Если эта оценка не может быть улучшена, то она называется «постоянной пометкой» и обозначается . В противном случае она называется «временной пометкой». Обозначим через y номер вершины, получившей постоянную пометку последней. Алгоритм состоит из трех шагов.

Шаг 1. Всем узлам, кроме исходного, приписываются временные пометки, равные , т.е. . Исходному узлу приписывается постоянная пометка, равная нулю, т.е. и .

Шаг 2. Рассматриваем все вершины j, смежные с последней получившей постоянную пометку вершиной и имеющие временные пометки. Сравниваем величину временной пометки с суммой величины последней постоянной пометки и длины дуги , ведущей из y в рассматриваемую вершину. Временной пометке рассматриваемого узла присваиваем минимальное значение из двух сравниваемых величин:

.

Среди всех временных пометок выбираем минимальную (пусть это пометка вершины ) и делаем ее постоянной, т.е. и . Кроме того, помечаем дугу , ведущую в выбранную на данном этапе вершину. Если все временные пометки равны бесконечности, т.е. , то в исходном графе отсутствует путь из S в эти вершины и вычисления заканчиваются.
Шаг 3. Если последняя постоянная пометка приписана узлу Т , то алгоритм завершает работу: кратчайший путь из вершины S в узел назначения Т найден. Иначе повторяем шаг 2.

В процессе решения помеченные дуги образуют в исходном графе ориентированное дерево кратчайших путей с корнем в вершине S – т.е. путь от вершины S до любой вершины, принадлежащей дереву, – кратчайший. Кроме этого, если вершина y принадлежит кратчайшему пути из S в j, то часть этого пути, заключенная между у и j, является кратчайшим путем из вершины у в j.

Алгоритм Дейкстры может быть выполнен непосредственно на сети.

Пример. Сеть дорог с двухсторонним движением задана матрицей расстояний в км (матрицей весовых коэффициентов). Необходимо найти для данной сети дорог самый короткий маршрут из пункта 1 в пункт 10.

Узлы

Решение

Схематически сетевая модель задачи изображена на рис. 6.3 в виде неориентированной сети.

Рис. 6.3 Сетевая модель задачи.

Продемонстрируем работу алгоритма Дейкстры, отмечая временные и постоянные пометки непосредственно в узлах сети. Для этого каждый узел изобразим в виде овала и разделим его на три части следующим образом

Шаг 1. Исходному узлу приписываем постоянную пометку, равную нулю, т.е. и . Всем остальным узлам, приписываем временные пометки, равные , т.е. , j=2,…,8. Отметим это на сети:

Шаг 2. Узлы 2, 3 и 6 смежные с последним, получившим постоянную пометку узлом 1. Новые значения временных пометок этих узлов будут:

Минимальной временной пометкой является пометка узла 2, т.к. поэтому она становится постоянной. Подчеркиваем ее и Помечаем дугу . Отметим это на сети:

Шаг 3. Поскольку узел 8 не помечен постоянной пометкой, переходим к шагу 2.

Шаг 2. Узлы 4, 5, 6 и 7 смежные с последним, получившим постоянную пометку узлом 2. Новые значения временных пометок этих узлов будут:

Минимальной временной пометкой является пометка узла 3, т.к. поэтому она становится постоянной. Подчеркиваем ее и Помечаем дугу . Отметим это на сети:

Шаг 3. Поскольку узел 8 не помечен постоянной пометкой, переходим к шагу 2.

Шаг 2. Узлы 5, 6 и 8 смежные с последним, получившим постоянную пометку узлом 3. Новые значения временных пометок этих узлов будут:

Минимальной временной пометкой является пометка узла 4, т.к. поэтому она становится постоянной. Подчеркиваем ее и Помечаем дугу . Отметим это на сети:

Шаг 3. Поскольку узел 8 не помечен постоянной пометкой, переходим к шагу 2.

Шаг 2. Узлы 5 и 7 смежные с последним, получившим постоянную пометку узлом 4. Новые значения временных пометок этих узлов будут:

Минимальной временной пометкой является пометка узла 7, т.к. она становится постоянной. Подчеркиваем ее и Помечаем дугу . Отметим это на сети:

Шаг 3. Поскольку узел 8 не помечен постоянной пометкой, переходим к шагу 2.

Шаг 2. Узлы 5 и 8 смежные с последним, получившим постоянную пометку узлом 7. Новые значения временных пометок этих узлов будут:

Минимальной временной пометкой является пометка узла 8, т.к. она становится постоянной. Подчеркиваем ее и Помечаем дугу . Отметим это на сети:

Шаг 3. Поскольку узел 8 помечен постоянной пометкой, то алгоритм завершает работу: кратчайший путь из узла 1 в узел назначения 8 найден.

Построенное дерево кратчайших путей состоит из дуг (1,2), (1,3), (2,4), (4,7), (7,8) (они помечены на последней сети). Кратчайший путь от узла 1 до узла 8 составляет 8 км, т.к. постоянная пометка этого узла и состоит из дуг (1,2), (2,4), (4,7), (7,8).

ЧАСТЬ ВТОРАЯ

ЭКОНОМЕТРИКА