Задача определения кратчайшего пути
Задача состоит в том, чтобы найти кратчайший путь на графе от какой-то выделенной вершины до любой другой.
Пример: узел 7 – склад, остальные узлы – строительные площадки компании. Показатели на дугах расстояния в километрах.
Надо найти кратчайшие расстояния от склада до каждой строительной площадки. Какова длина кратчайшего пути от склада до строительной площадки 1? Проходит ли кратчайший путь от склада до строительной площадки 1 через строительную площадку 2?
Решим эту задачу методом присвоения меток. Каждому узлу присваиваем метку из двух чисел. Первое число – это минимальное расстояние от узла 7 до данного узла, второе – номер предыдущего узла. Если кратчайшее расстояние от узла 7 определено, то соответствующая метка называется постоянной. Она закрашивается и обозначается круглыми скобками. Все остальные метки – временные, обозначаются квадратными скобками.
Изначально узлу 7 присваиваем метку (0,S), где 0 – расстояние от узла 7 – обозначение стартового узла.
Узел 7 связан с узлами 2,4,6. Длины соответствующих ребер – 17,5,6. Поэтому узлам 2,4,6 присваиваем временные метки -- .
Временная метка с наименьшим расстоянием до узла 7 становится постоянной. Это метка (5,7) узла 4. Поэтому следующий шаг начинаем с узла 4.
Узел 4 связан с узлами 2 и 5 без постоянных меток. Длина ребра 4 -- 5 равна 4, метка узла 4 – (5,7) временная метка узла 5 равна
. Длина ребра 4 -- 2 равна 6, метка узла 4 – (5,7)
временная метка узла 2 равна
. Узел 2 помечен меткой
, но 11<17
старую метку
узла 2 меняем на новую временную метку
, где 11 – длина пути от узла 7 до узла 2, 4 – номер предшествующего узла.
После этого из всех временных меток выбираем метку с наименьшим первым числом. Это
. Эта метка становится постоянной, а очередной шаг начинаем с узла, соответствующего этой метке, -- узла 6.
Этот узел связан с узлом 5 без постоянной метки. Длина ребра 6-5 равна 2, метка узла 6 – (6,7) временная метка узла 5 равна
. Но узел 5 уже помечен меткой
. Так как 8<9, то узлу 5 припишем новую метку
. После этого из всех временных меток
метку с наименьшим первым числом
объявим постоянной, а следующий шаг начнем с соответствующего ей узла 5.
Узел 5 связан только с одним узлом без постоянной метки – узлом 3. Длина ребра 5-3 равна 4, метка узла 5 --
временная метка узла 3 равна
. Теперь из временных меток
метку с наименьшим первым числом
объявляем постоянной, а следующий шаг начнем с соответствующего ей узла 2.
Узел 2 связан с узлами 1 и 3 без постоянных меток. Длина ребра 2-1 равна 15, метка узла 2 --
узлу 1 припишем временную метку
. Длина ребра 2-3 равна 3, метка узла 2 --
можно пометить узел 3 временной меткой
, но узел 3 уже помечен меткой
с меньшим первым числом. Поэтому метку 3 не меняем. Теперь из временных меток
метка с наименьшим первым числом становится постоянной
, а с соответствующего ей узла 3 начнем следующий шаг. Метку узла 1 меняем на
. Всем узлам приписаны постоянные метки. Действие алгоритма прекращается.
Первое число метки у каждой вершины – это длина кратчайшего пути от узла 7 до данной вершины. Чтобы восстановить кратчайший путь от узла 7 до какой-то вершины, нужно из этой вершины перейти в соседнюю (ее номер – это второе число метки). И так до вершины 7.
Теперь можно ответить на вопросы задачи. Метка узла 1 --
длина кратчайшего пути от узла 7 до узла 1 равна 22. Из узла 1 идем в узел 3. Метка узла 3 --
идем в узел 5. Метка узла 5 --
идем в узел 6. Метка узла 6 --
идем в узел 7, т.е. кратчайший путь 1-3-5-6-7. Он не проходит через узел 2.
Задачи.
1. Компания грузовых перевозок осуществляет услуги по перевозке грузов между Воронежем (В) и райцентрами. Так как существенны быстрое обслуживание и минимальные транспортные затраты, то необходим наиболее короткий маршрут. Рисунок отображает сеть дорог. Расстояния указаны в километрах. Найти кратчайшие маршруты от Воронежа до всех 10 райцентров. Какова длина кратчайшего пути от Воронежа до райцентра 10? Проходит ли кратчайший путь от Воронежа до райцентра 9 через райцентр 6?
2. Предложить алгоритм действий при наличии в сети нескольких равных постоянных меток.