ЗАДАЧА ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО МАРШРУТА В СЕТИ

Пусть требуется найти кратчайший маршрут в сети, ведущий от исходного узла к каждому из узлов сети.

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

Первый этап.

1. Исходному узлу, относительно которого определяется кратчайший маршрут, присваивается постоянная метка (0, И). Т. е. значения метки показывают, что данный узел является точкой отсчета маршрута и является исходным узлом сети. Всем узлам, которые непосредственно связаны с исходным узлом (т. е. соединены одним ребром), присваиваются временные метки . Из этих меток постоянной становится та, для которой число минимально. Если меток с минимальным числом несколько, то любую из них можно выбрать в качестве постоянной.

2. Рассматривается очередной узел k, которому присвоена постоянная метка. Всем узлам, которые непосредственно связаны с узлом k и не имеют постоянных меток, присваиваются временные метки, значения которых вычислено от узла k.

3. Из всех временных меток, постоянной становится та, для которой число минимально. Если меток с минимальным числом несколько, то любую из них можно выбрать в качестве постоянной.

4. Алгоритм повторяется, начиная с пункта 2, пока всем узлам не будут присвоены постоянные метки.

Второй этап.

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

Покажем, как исполняется описанный алгоритм, на следующем примере.

Рассмотрим сеть, заданную на рис. 1, с выделенным узлом 1. Цифры на ребрах, связывающих два узла, есть расстояния между этими узлами.

Рис. 1

Первый этап.

1-й шаг. Узлу 1 присваиваем постоянную метку (узел с постоянной меткой выделяется, например, более жирной обводкой кружка). Всем узлам, которые соединены с выделенным узлом 1 одним ребром, присваиваем временные метки так, как это показано на рис. 2 – первое число в метке S равно расстоянию от помеченного узла до узла 1, второе число в метке X номер предшествующего узла.

Из полученных временных меток выбираем метку с минимальным первым числом, и делаем ее постоянной, так это показано на рис. 3. Таким образом, по окончании первого шага узлы 1 и 4 имеют постоянные метки, узлы 2 и 3 – временные метки, а узлы 5, 6, 7, 8 и 9 никаких меток не имеют.

Рис. 2	Рис. 3

2-й шаг. Каждому узлу, который соединен с узлом 4 одним ребром, присваиваем временную метку по следующему правилу:

а) = первое число метки узла 4 + длина ребра от узла 4 до соответствующего узла;

б) = 4 указывает на то, что число есть длина пути от исходного узла до рассматриваемого и проходящего через узел 4.

Результат присвоения временных меток представлен на рис. 4. Сравниваем все имеющиеся на данном этапе временные метки. Из них постоянной делаем метку, первое число которой минимально. Это метка узла 3 (16, 1). Делаем ее постоянной (рис. 5).

Замечание: узел 3 имел две временные метки, поэтому вторую метку вычеркиваем или удаляем.

Рис. 4	Рис. 5

Таким образом, по окончанию второго шага узлы 1, 3 и 4 имеют постоянные метки; узлы 2, 5 и 6 – временные; а узлы 7, 8 и 9 не имеют меток вообще.

3-й шаг. Каждому узлу, не имеющему постоянной метки и непосредственно связанному с узлом 3, присваиваем временную метку по следующему правилу:

а) = первое число метки узла 3 + длина ребра от узла 3 до соответствующего узла;

б) = 3 указывает на то, что число есть длина пути от исходного узла до рассматриваемого и проходящего через узел 3.

Результат присвоения временных меток представлен на рис. 6. Сравниваем все имеющиеся на данном этапе временные метки. Из них постоянной делаем метку, первое число которой минимально. Это метка узла 6 (19, 3). Делаем ее постоянной (рис. 7).

Рис. 6	Рис. 7

По окончанию третьего шага постоянные метки имеют узлы 1, 3, 4 и 6; узлы 2 и 5 – временные; а узлы 7, 8 и 9 не имеют меток.

4-й шаг. Каждому узлу, не имеющему постоянной метки и непосредственно связанному с узлом 6, присваиваем временную метку:

а) = первое число метки узла 6 + длина ребра от узла 6 до соответствующего узла;

б) = 6 указывает на то, что число есть длина пути от исходного узла до рассматриваемого и проходящего через узел 6.

Результат присвоения временных меток представлен на рис. 8. Сравниваем все имеющиеся на данном этапе временные метки. Из них постоянной делаем метку, первое число которой минимально. Это метка узла (20, 1). Делаем ее постоянной (рис. 9).

Рис. 8	Рис. 9

В результате, по окончанию четвертого шага постоянные метки имеют узлы 1, 2, 3, 4 и 6; узлы 5, 7, 8 и 9 – временные.

5-й шаг. Каждому узлу, не имеющему постоянной метки и непосредственно связанному с узлом 2, присваиваем временную метку.

а) = первое число метки узла 2 + длина ребра от узла 2 до соответствующего узла;

б) = 2 указывая на то, что число есть длина пути от исходного узла до рассматриваемого и проходящего через узел 2.

Результат присвоения временных меток представлен на рис. 8. Сравниваем все имеющиеся на данном этапе временные метки. Из них постоянной делаем метку, первое число которой минимально. Это метка узла 5 (24, 2). Делаем ее постоянной (рис. 9).

Рис. 8	Рис. 9

В результате, по окончанию пятого шага постоянные метки имеют узлы 1, 2, 3, 4, 5 и 6; узлы 7, 8 и 9 – временные.

6-й шаг. Каждому узлу, не имеющему постоянной метки и непосредственно связанному с узлом 5, присваиваем временную метку.

Результат присвоения временных меток представлен на рис. 10. Сравниваем все имеющиеся на данном этапе временные метки. Из них постоянной делаем метку, первое число которой минимально. Это метка узла 7 (25, 6). Делаем ее постоянной (рис. 11).

Рис. 10	Рис. 11

В результате, по окончанию шестого шага постоянные метки имеют узлы 1, 2, 3, 4, 5, 6 и 7; узлы 8 и 9 – временные.

7-й шаг. Каждому узлу, не имеющему постоянной метки и непосредственно связанному с узлом 7, присваиваем временную метку.

Результат присвоения временных меток представлен на рис. 12. Сравниваем все имеющиеся на данном этапе временные метки. Из них постоянной делаем метку, первое число которой минимально. Это метка узла 9 (29, 6). Делаем ее постоянной (рис. 13).

Рис. 12	Рис. 13

В результате, по окончанию шестого шага постоянные метки имеют узлы 1, 2, 3, 4, 5, 6, 7 и 9; узел 8 – временные.

8-й шаг. Так как узел 9 непосредственно не связан ни с одним узлом, имеющим временные метки, а в сети еще остались узлы, не имеющие постоянных меток, то возвращаемся к рассмотрению узла 7, от которого уже отсчитаны временные метки. Из всех временных меток постоянной делаем ту, первое число которой минимально. Это метка узла 8 (31, 6). Делаем ее постоянной (рис. 14).

Рис. 14

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

Второй этап.

По второму числу метки, от каждого узла находим маршрут до исходного узла, который будет минимальным для данной сети. Покажем это на примере. Рассмотрим узел 8. Второе число в метке, указывает на то, что кратчайший маршрут от узла 1 к узлу 8 лежит через узел 6. Переходим к узлу 6. Второе число метки этого узла показывает, что кратчайший маршрут от узла 1 к узлу 6 лежит через узел 3. Второе число метки узла 3 указывает, что кратчайший путь непосредственно связывает его с узлом 1. Таким образом, кратчайший маршрут от узла 1 к узлу 8 есть: 1-3-6-8.

В результате второго этапа можно сделать вывод, что существуют пять маршрутов соединяющие все узлы сети с узлом 1: а) 1-2-5; б) 1-4; в) 1-3-6-7; г) 1-3-6-8; д)1-3-6-9.

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: