Материал: АиСД. Практикум (in dev)

Записываем выражения для функции f_i

f₁ +3 f₁ + 4 f₁ + 2

f1 = 0; f2 = min; f3 = min; f4 = min f5 + 5

f₆ + 3 f₆ + 6 f₆ + 2

f₂ + 3

_f4 + 5 f₃ + 6

f₆ + 1 f₄ + 2 f₅ + 6

f₅ = min ; f₆ = min ; f₇ = min

f₉ +12 f₅ + 1 f₆ + 8

f₇ + 6 f₇ + 8

f₈ + 7

f₇ + 4

f₆ + 7 f₅ + 12

f₈ = min ; f₉ = min ; f₁₀ = min f₈ + 3 .

f₉ + 6 f₈ + 6

f₉ + 11

Указанные целевые функции , представляют собой систему линейных алгебраических уравнений (в примере имеется 10 уравнений и 10 неизвестных).

Рассмотрим один из вариантов ее решения, учитывая, что f₁ = 0 .

Тогда имеем:

2

f₂ = 3; f₃ = 4; f₄ = min f₅ + 5 = 2;

f₆ + 2

6

7 10

f₆ + 1 7 4 4

f₅ = min f₉ +12 = min ; f₆ = min f₅ +1 = min = 4

f₇ + 6 f₆ + 1 f₇ + 1 f₅ + 1

f₈ + 7

Подставив выражение для f₆ в f₅, получим

7 f₅ = min 4 + 1 = 5.

f₅ + 1 + 1

Тогда

11 17 15

f₇ = 11; f₈ = min ; f₉ = min ; f₁₀ = min f₈ + 3 .

f₉ + 6 f₈ + 6 f₉ + 11

Подставляя f₉ в f₈, получаем

11

f₈ = min 17 + 6 = 11.

f₈ + 6 + 6

Окончательно имеем: f₉ = 17; f₁₀ = 14.

39. Метод Дейкстры

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

Найти кратчайший путь на графе от вершины L до вершины D (рис.2).

Рис.2. Взвешенный неориентированный граф

Запишем алгоритм в виде последовательности шагов.

Шаг 1. Определяются расстояния от начальной вершины L до всех остальных .

Шаг 2. Выбираем наименьшее расстояние от L до B, найденная вершина В прини-

мается за вновь выбранную. Найденное наименьшее расстояние добавляется к длинам ребер

от новой вершины В до всех остальных. Выбирается минимальное расстояние от В до N. Новая вершина N принимается за выбранную.

Для наглядности в дальнейшем вместо знака ∞ будем ставить знак “-“.

Шаг 3. Определяются расстояния от вершины N до всех оставшихся (за исключением

L и B) .

Расстояние от вершины L через вершину N до вершины G равно 18. Это расстояние

больше, чем расстояние LB+BG= 16, поэтому оно не учитывается в дальнейшем.

Продолжая аналогичные построения, построим таблицу. Таким образом, найдена

длина кратчайшего пути между вершинами L и D (44 условных единицы).

Траектория пути определяется следующим образом.

Осуществляем обратный просмотр от конечной вершины к начальной.

Просматриваем столбец, соответствующий вершине, снизу вверх и фиксируем первое появление минимальной величины. В столбце, соответствующем вершине D, впервые минимальная длина 44 появилась снизу в четвертой строке. В этой строке указана вершина S, к которой следует перейти, то есть следующим нужно рассматривать столбец, соответствующий вершине S.