Задача о кратчайшем пути

Дан сетевой график, в котором каждой дуге поставлена в соответствие ее длина L_ij. Порядок нумерации вершин не имеет значения, но в приведенной нумерации задача состоит в определении кратчайшего пути из вершины 1 в вершину 7. Модель задачи включает критерий - длину искомого пути

, где - путь от вершины 1 к вершине 7, и граф сети (или описывающую его матрицу). Применение метода ДП правомерно, так как задача представима как многошаговая: искомый путь есть допустимая графом последовательность дуг, а выбор дуги рассматриваем как один шаг задачи. Состояние полностью определяется номером вершины, а число шагов от конкретной вершины до 7-й неоднозначно. Учитывая эти особенности, вводим последовательность функций { f_i }, i =1,7 так, что каждая функция есть минимальная длина пути от i -й вершины в 7-ю: , где - мн-во всех допустимых путей из i -й вершины в 7-ю.

Для составления функционального уравнения возьмем произвольную вершину i (i №7) и будем определять путь из нее в вершину 7. Из этого пути выделим один шаг - выбор вершины, следующей за i -й. Множество дуг, выходящих из вершины i, обозначим . Взяв произвольную дугу из множества ,окажемся в смежной вершине j, длина пути до которой равна L_ij. Длина пути от i -й вершины до 7-й будет равна L_ij + f_j. Так как она зависит только от j, то выбором j можно ее минимизировать. Рекуррентное соотношение: . Начинать условную оптимизацию следует с определения f ₇. Так как f ₇ - минимальная длина пути из вершины 7 в саму себя, то f ₇=0. Вычислять можно те функции f_i, для которых уже известны все f_j, ij О . Поэтому следующей можно находить только функцию f ₆: f ₆ = min (L ₆₇ + f ₇)=1+0=1.

В приведенных формулах подчеркнуты индексы, на которых достигается минимум. Из расчета видно, что длина кратчайшего пути из вершины 1 в вершину 7 равна 11. Найдем оптимальный путь: из f ₁: первая часть пути лежит на дуге 1-2, значит, новое состояние - это вершина 2; из f ₂ находим следующую часть пути - дугу 2-5 и очередное состояние - вершину 5; поэтому далее обращаемся к f ₅ и достраиваем оптимальный путь дугой 5-6 и, наконец, заканчиваем дугой 6-7. Весь путь: 1®2®5®6®7. На этапе безусловной оптимизации просматривались не все функции f_i, что отличает данную задачу. Имея результаты условной оптимизации, можно легко найти кратчайшие пути из любой вершины сети в вершину 7.