Метод присвоения меток

Задача состоит в том, чтобы найти кратчайший путь на графе от какой-то выделенной вершины до любой другой вершины.

 

Пример: Узел 7 – склад, остальные узлы – строительные площадки компании. Показатели на дугах – расстояния в километрах.

Надо найти кратчайшие расстояния от склада до каждой строительной площадки.

Какова длина кратчайшего пути от склада до строительной площадки 1?

Проходит ли кратчайший путь от склада до строительной площадки 1 через строительную площадку 2?

Какова длина кратчайшего пути от склада до строительной площадки 2?

Проходит ли кратчайший путь от склада до строительной площадки 2 через строительную площадку 4?

 

Каждому узлу приписывают метку из двух чисел:

- первое число – минимальное расстояние от узла 7 до данного узла,

- второе – номер предыдущего узла на пути от узла 7 к данному узлу.

Помеченным называют узел, для которого определен путь от узла 7. Иначе узел – непомеченный.

Если кратчайшее расстояние от узла 7 до данного узла определено, то соответствующая метка постоянная и обозначается в круглых скобках. Остальные метки временные и обозначаются в квадратных скобках. Узлы с постоянными метками закрашиваем.

Узлу 7 присваиваем метку (0, S), где 0 – расстояние от узла 7, S – обозначение стартового узла.

Узел 7 связан с узлами 2, 4 и 6. Им присваиваем соответствующие метки – [17, 7], [5, 7], [6, 7].

После выполнения этой операции выполняют два шага:

- находят участок минимальной длины и соответствующую временную метку делают постоянной;

- узел, которому соответствует данная постоянная метка становится новым стартом.

 

Метка с наименьшим расстоянием [5, 7] соответствует узлу 4. Этот узел объявляем помеченным и заменяем скобки у метки.

Узел 4 связан непосредственно с узлами 2 и 5 без постоянных меток. Временная метка узла 5 равна [5+4, 4]=[9, 4], а у узла 2 – [5+6, 4]= [11, 4]. Т.к. узел 2 уже имеет временную метку [17, 7], то из двух меток выбираем ту, в которой расстояние меньше, т.е. [11, 4].

Из всех временных меток [11, 4], [9, 4], [6, 7] выбираем метку с наименьшим первым числом – [6, 7]. Она становится постоянной и очередной шаг начинаем с узла 6.

Этот узел связан только с узлом 5 без постоянной метки. Временная метка узла 5 равна [6+2, 6]=[8, 6]. Эта метка имеет меньшее первое число, чем предыдущая, поэтому узлу 5 приписываем новую временную метку [8, 6].

Из всех временных меток [11, 4], [8, 6] метку с наименьшим первым числом [8, 6] объявляем постоянной и следующий шаг начинаем с соответствующего ей узла 5.

Узел 5 связан только с одним узлом без постоянной метки – узлом 3. Временная метка узла 3 равна [8+4, 5]=[12, 5].

Из всех временных меток [11, 4], [12, 5] метку с наименьшим первым числом [11, 4] объявляем постоянной и следующий шаг начинаем с соответствующего ей узла 2.

Узел 2 связан с узлами и 1 и 3 без постоянных меток. Временная метка узла 1 равна [11+15, 2]=[26, 2], а узла 3 – [11+3, 2]=[14, 2]. Т.к. узел 3 уже помечен меткой с меньшим первым числом, то метку не меняем.

Из временных меток [26, 2], [12, 5] метка с наименьшим первым числом [12, 5] становится постоянной и следующий шаг начинаем с соответствующего ей узла 3.

Метку узла 1 меняем на (12+10, 3)=(22, 3).

Всем узлам приписаны постоянные метки. Действие алгоритма прекращается.

Первое число метки у каждой вершины – это длина кратчайшего пути от узла 7 до данной вершины. Чтобы восстановить кратчайший путь от узла 7 до какой-то вершины, нужно из этой вершины перейти в соседнюю (ее номер – второе число метки) и т.д. до вершины 7.

Ответы на вопросы задачи:

Метка узла 1 – (22, 3), следовательно, длина кратчайшего пути от узла 7 до узла 1 равна 22. Чтобы определить путь, смотрим второе число метки: из узла 1 идем в узел 3. Метка узла 3 – (12, 5), следовательно, идем в узел 5. Метка узла 5 – (8, 6), следовательно, идем в узел 6. Метка узла 6 – (6, 7), следовательно, идем в узел 7. Т.о., кратчайший путь 1-3-5-6-7. Он не проходит через узел 2.

Два других вопроса – на самостоятельное рассмотрение.