Задача определения кратчайшего пути

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

> ПРИМЕР 1.8. Узел 7 (рис 1.9) - склад, остальные узлы - строительные площадки компании. Показатели на дугах - расстояния в километрах.

Надо найти кратчайшие расстояния от склада до каждой строительной площадки. Какова длина кратчайшего пути от склада до строительной площадки 1? Проходит ли кратчайший путь от склада к строительной площадке 1 через строительную площадку 2? Какова длина кратчайшего пути от склада до строительной площадки 2? Проходит ли кратчайший путь от склада к строительной площадке 2 через строительную площадку 4?

Рис. 1.9

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

Итак, узлу 7 приписываем метку (О, S) (рис. 1.10), где 0 - это расстояние от узла 7, S- обозначение стартового узла.

Рис. 1.10

Узел 7 связан с узлами 2, 4, 6. Длины соответствующих ребер - 17, 5, 6. Поэтому узлам 2, 4, 6 присваиваем временные метки - [17, 7], [5, 7], [6, 7] соответственно (рис. 1.11, первое число - длина пути от узла 7 до данного узла, а второе - предшествующий узел).

После выполнения этой операции можно сделать два следующих шага:

  • 1) найти участок (участки) минимальной длины и соответствующую временную метку (метки) сделать постоянной;
  • 2) узел (узлы), которому соответствует появившаяся постоянная метка, становится новым стартом.

После выполнения этой операции временная метка с наименьшим расстоянием до узла 7 становится постоянной. Это метка (5, 7) узла 4 (см. рис. 1.11). Поэтому следующий шаг мы начнем с узла 4.

Рис. 1.11

Узел 4 непосредственно связан с узлами 2 и 5 без постоянных меток. Длина ребра 4-5 равна 4, метка узла 4 - (5, 7), временная метка узла 5 равна [5 + 4, 4] = [9,4] (рис. 1.12). Длина ребра 4-2 равна 6, метка узла 4 - (5,7), временная метка узла 2 равна

[5 + 6, 4] = [11, 4]. Таким образом, мы нашли путь от узла 7 до узла 2 длины 11.

Узел 2 ранее был помечен меткой [17, 7] (путь длины 17), но 11<17, значит, старую метку [17, 7] узла 2 мы заменяем новой временной меткой [11, 4], где 11 - это длина пути от узла 7 до узла 2, а 4 - номер предшествующего узла.

После этого из всех временных меток [11,4], [9, 4], [6, 7] выбираем метку с наименьшим первым числом. Это [6, 7]. Эта метка становится постоянной (6, 7), а очередной шаг мы начнем с узла, соответствующего этой метке, - узла 6.

Рис. 1.12

Этот узел связан с узлом 5 без постоянной метки. Длина ребра 6-5 равна 2, метка узла 6 - (6, 7), временная метка узла 5 равна [6 + 2, 6] = [8, 6]. Но узел 5 уже помечен меткой [9, 4]. Так как 8 < 9, то узлу 5 припишем новую метку - [8, 6]. После этого из всех временных [11, 4] и [8, 6] метку с наименьшим первым числом (8, 6) (рис. 1.13) объявляем постоянной, а следующий шаг начнем с соответствующего ей узла 5.

Рис. 1.13

Узел 5 связан только с одним узлом без постоянной метки - узлом 3. Длина ребра 5-3 равна 4, метка узла 5 - (8, 6), следовательно, временная метка узла 3 равна [8 +4, 5] = [12, 5] (рис. 1.14). Теперь из всех временных меток [11,4] и [12, 5] метку с наименьшим первым числом [11, 4] объявляем постоянной, а следующий шаг начнем с соответствующего ей узла 2.

Рис. 1.14

Узел 2 связан с узлами 1 и 3 без постоянных меток. Длина ребра 2-1 равна 15, метка узла 2 - (11, 4) (рис. 1.15), следовательно, узлу 1 припишем временную метку [11 + 15] = [26, 2]. Длина ребра 2-3 равна 3, метка узла 2 - (11, 4), следовательно, мы могли бы пометить узел 3 меткой [11 + 3, 2] = [14, 2], но узел 3 не меняем (стоит постоянная метка). Теперь из временных меток [26, 2] и [12, 5] метка с наименьшим первым числом становится постоянной (12, 5), а с соответствующего ей узла 3 начнем следующий шаг. Метку узла 1 меняем на (12 + 10, 3) = (22, 3). Всем узлам приписаны постоянные метки. Действие алгоритма прекращается.

Рис. 1.15

Первое число метки у каждой вершины - это длина кратчайшего пути от узла 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. Ответы на два других вопроса оставляем читателю в качестве упражнения.

Задача 1.3. Компания грузовых перевозок осуществляет услуги по перевозке грузов между Воронежем (В) и райцентрами. Если компания получает заказ на обслуживание, она как можно быстрее посылает грузовик в райцентр, из которого поступил заказ. Так как существенны быстрое обслуживание и минимальные транспортные затраты, большое значение приобретает то, что грузовик проследует из Воронежа в соответствующий райцентр по наиболее короткому маршруту. Сеть, представленная на рис. 1.16, отображает сеть дорог. Расстояния указаны в километрах.

Рис. 1.16

Найти кратчайшие маршруты от Воронежа до всех 10 райцентров. Какова длина кратчайшего пути от Воронежа до райцентра 10? Какова длина кратчайшего пути от Воронежа до райцентра 8? Проходит ли кратчайший путь от Воронежа до райцентра 9 через райцентр 6?

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >