При перевозке груза из пункта А в пункт В мы хотим выбрать оптимальный маршрут. Эта задача может рассматриваться как задача поиска пути в граф — кратчайший путь. Здесь вершинами графа могут быть города, железнодорожные станции, перекрестки и т. д., а ребрами графа являются дороги.
Рассмотрим пример. Задан неориентированный граф, имеющий 16 вершин.
Как можно попасть из вершины 1 в вершину 16? Здесь можно воспользоваться путём 1→2→3→4→8→12→16, а можно1 →2→6→10→11→15→16. Если на каждом шаге мы идем только вверх или вправо, то всего в этом примере имеются 20 возможных путей из вершины 1 в вершину 16. Иногда может быть выгодно разрешить двигаться не только вверх или вправо. В этом случае число путей увеличится. Так, возможен вариант 1→2→6→5→9→10→11→12→16. Нашей задачей является нахождение кратчайшего пути, ведущего из одной вершины в другую.
Получили следующую математическую задачу.
Дан ориентированный граф, каждому ребру приписана некоторая длина. Длина пути из одной вершины в другую равна сумме длин ребер, входящих в этот путь. Необходимо найти кратчайший из путей, ведущих из вершины А в вершину В.
Такая задача может возникнуть в различных ситуациях. Например, если мы захотим перевезти груз, то ребра графа — это дороги, а вершины графа — города, стоящие на перекрестках путей. Длины ребер определяются условиями задачи. Если мы хотим найти самый дешевый путь, то за длину ребра нужно взять стоимость перевозки груза по этому ребру. Если мы хотим найти самый быстрый путь, то в качестве длины надо взять время проезда. Если самый короткий — расстояния между соответствующими городами.
В частности, задача о кратчайшем пути возникает при рассмотрении задачи об использовании оборудования.
Рассмотрим пример. Пусть наше производство в течение года нуждается в автомобиле. Нам представляются различные возможности. Например, мы можем арендовать автомобиль на определенный срок по определенной стоимости. Мы можем купить автомобиль, какое-то время им пользоваться, а затем продать, и т.д. Ставится задача разработать самый дешевый план использования оборудования на указанный период времени. Здесь вершинам графа соответствуют моменты времени, а каждой имеющейся возможности (в каждый момент времени) будет соответствовать ребро графа. Может быть несколько ребер, соединяющих одну и ту же пару вершин. За длину ребра нужно принять стоимость выбранного варианта. Можно проиллюстрировать сказанное следующим рисунком. Здесь точки на прямой соответствуют последовательным моментам времени, отрезки и дуги соответствуют наличию ребра (варианта), аij стоимость соответствующего варианта использования автомобиля на интервале времени [i,j].
Алгоритм расстановки меток.
Нахождение длин кратчайших путей, выходящих из вершины А, будем производить, используя алгоритм расстановки меток. В процессе работы алгоритма каждой вершине будет приписано некоторое число, в дальнейшем эти числа мы будем называть метками. Если какой-то вершине приписана метка, равная d, то это значит, что существует путь из вершины А в эту вершину длиной d. Если найден более короткий путь, то значение метки заменяется на меньшее. Метки могут быть временными или постоянными. Постоянные метки будем отмечать значком *, не отмеченные таким значком — временные. Например, li — временная, а l*i- постоянная. Метка становится постоянной в том случае, если она соответствует самому короткому пути из вершины А в данную вершину. Задача решена, если все метки стали постоянными.
Итак, выпишем шаги нашего алгоритма.
/ шаг. Каждой вершине i приписываем некоторое число li, равное длине самого короткого известного на данный момент пути из вершины А в данную вершину. Вначале это lA =0, a l2 = l3 =…= lB =∞Не ограничивая общности можно считать, что вершине А соответствует вершина с номером l, а вершине В — вершина с самым большим номером. На данном этапе все метки временные.
2 шаг. Среди временных меток ищем минимальную. Например, это вершина i. Просматриваем все ребра, выходящие из вершины i, и проверяем выполнение неравенства
li+aij