2.4.1. Алгоритм Дийкстры

Рассматриваемый здесь алгоритм предназначен для поиска кратчайших путей из заданного узла sв каждый из остальных узлов в случаеa_ij0и основан на так называемом «методе пометок». Каждый узел графаiимеет меткуd(i), которая на каждой итерации алгоритма представляет собой длину кратчайшего найденного пути в узелi. Поэтому перед началом работы алгоритмаd(s)=0, d(i)= приis. Еще одна меткаl(i)вводится для того, чтобы по окончании работы алгоритма было возможно вычислить последовательность вершин, образующих каждый из кратчайших путей.

Пусть d(i) - метка узла,S– множество вершин.

Шаг 1. Положить d(s)=0, d(i)= приis,l(i)=0,S=

Шаг 2. Если в Sвходят все вершины графа, то СТОП: длины кратчайших путей найдены.

Шаг 3. Если для всех iSd(i)= ,то СТОП: не существует путей в вершины, не входящие вS. Иначе среди вершинiSнайти вершинуnс минимальной меткой.

Шаг 4. Включить вершину nв множествоS, для всехkSвычислитьd(k)=min{d(k),d(n)+a_nk}. Если при этом значениеd(k)изменяется, тоl(k) положить равнымn. Перейти к шагу 2.

Пример 1.

В этом алгоритме последовательно просматриваются все вершины графа, причем каждый раз выбирается вершина с минимальной меткой из еще не просмотренных (при первой итерации будет выбрана вершина s), и затем для соседних с ней вершин вычисляются новые значения меток как минимальные из двух чисел: прежняя метка и длина вновь найденного пути через рассматриваемую вершину.

Легко видеть, что в случае a_ij0 минимальная метка для непросмотренных вершин уже не может быть уменьшена в дальнейшем и является длиной кратчайшего пути в эту вершину. После выполнения алгоритма с помощью метокl(i) могут быть найдены кратчайшие пути. Так, для пути изsвtпоследней будет вершинаt, предпоследней –l(t),перед ней –l(l(t)), и так далее, доs. Все такие пути образуют дерево кратчайших путей из вершиныs.

Рис. 2.7

Пример 2. Задача о покупке автомобиля. При решении вопроса о том, через какое время следует производить покупку нового автомобиля, необходимо учитывать его стоимость и возрастающие эксплуатационные расходы. Рассматривается восьмилетний период времени. Предполагается, что решение о покупке нового автомобиля может приниматься в начале каждого года, исходя из затрат на его приобретение, эксплуатационных расходов на период, в течение которого автомобиль будет использоваться, и ликвидационной стоимостимашины в момент, когда она заменяется на новую. Предположим, что в начальный момент человек не имеет автомобиля, и что он собирается покупать новый автомобиль по крайней мере каждые 4 года.

Сеть для рассматриваемой задачи содержит 9 вершин (рис.2.7). Если в начале i-го года производится покупка автомобиля, а в началеj-го года автомобиль заменяется на новый, то данному варианту замены соответствует дуга(i,j).

Длина дугиa_ij(в данном случае – стоимость) вычисляется по формуле гдеP_i– стоимость автомобиля в началеi-го года,m_k– эксплуатационные расходы в течениеk-го года,S_j– ликвидационная стоимость автомобиля в началеj-го года. Оптимальному решению соответствует кратчайший путь из вершины 1 в вершину 9. В таблице приведены результаты вычислений по алгоритму Дийкстры метокd(i). Просмотренные узлы выделены.

Для минимизации общих затрат покупку автомобиля следует производить в начале первого, пятого и девятого годов. Затраты при этом составляют 11250$.