Модели задач транспортной логистики

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

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

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

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

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

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

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

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

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

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

узел (узлы), которому соответствует появившаяся постоянная метка, становится новой точкой отсчета.

Анализируем полученную ситуацию. Минимальное расстояние от склада у пункта 4, поэтому превращаем его метку в постоянную и помечаем его.

Рассматриваем узел 4 как новую точку отсчета, он непосредственно связан с узлом 2 и 5. Найдем и проставим соответствующие временные метки: для узла 2 – [5+6, 4]=[11, 4]; для узла 5 – [5+4, 4]=[9, 4]. Метка на втором узле уже есть, сопоставим ее с новой. Так как расстояние на новой метке меньше, т.е. 11< 17, то старую метку заменяем новой. Затем снова анализируем все оставшиеся временные метки.

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