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

• Шаг 1. Полагаем S=V\{v0}, d(vi)=a(v0,vi) для всех i=1,…,k.
• Шаг 2. Если ½S½=1, то выполнить шаг 4. Выбрать в S элемент v’, для которого величина d(v’) является наименьшей (среди всех элементов из S).
• Шаг 3. Положить S=S\{v’}, d(v)=min{d(v), d(v’)+a(v’,v)} для всех vÎS и перейти к шагу 2.
• Шаг 4. Выдать d(v1),…,d(vk). Конец работы алгоритма.

 Алгоритм осуществляет «итеративный» процесс нахождения расстояния d(vi) для i=1,…,k. Проследим, как это делается для сети N, изображенной на рис. 1. Работа алгоритма будет иллюстрироваться заполнением таблицы 1.

При выполнении первого шага алгоритма величины d(vi) примут значения, которые указаны в нулевой строке таблицы. Из них точным является только d(v2), значения остальных величин завышены. На шаге 2 в качестве v’ выбирается вершина v2 (в таблице соответствующее значение набрано жирным шрифтом) и удаляется из S на шаге 3. На том же шаге уточняются предыдущие значения d(v) для vÎS (см. первую строку таблицы 6.1). На этом первый проход алгоритма заканчивается. На втором проходе в качестве v’ берется v5, удаляется из S и значения d(v) для vÎS снова уточняются. Результат уточнения отражен во второй строке таблицы. Когда множество S будет содержать только вершину

Рис. 1

Таблица 1

V3 алгоритм заканчивает работу. Результат: d(v1)=3, d(v2)=1, d(v3)=4, d(v4)=4, d(v5)=3.

Поскольку на каждом проходе алгоритма число элементов множества S уменьшается на единицу, то алгоритм Дейкстры всегда заканчивает работу. Следующее утверждение показывает, что он выдает «то что нужно».

Теорема 1  Пусть для сети N и фиксированной вершины v0 этой сети алгоритм Дейкстры выдал величины d(v1),…,d(vk). Тогда d(vi) есть расстояние от v0 до vi для i=1,…,k.

Доказательство. Отметим вначале, что если d(vi)¹ ¥ , то величина d(vi) равна длине некоторого пути из v0 в vi. Пусть в очередном проходе алгоритма на втором шаге выбирается вершина v’, d(v’)¹ ¥ и

v0=x0, x1,…,xi-1,xi,…,xp-1, xp=v’ –

кратчайший (v0,v’)–путь. Убедимся в том, что для любой вершины х этого пути выполняется равенство d(x)=d0(v0,x). Действительно, для х=х0 это справедливо. Предположим, что d(xi-1)=d(v0,x), но d(xi)>d(v0,xi). Тогда поскольку d(xi-1)<d(v’), то вершина хi-1 выбиралась на втором шаге в более раннем проходе алгоритма. На третьем шаге этого прохода d(xi) получило бы значение d(xi-1)+a(xi-1,xi), которое равно d(v0,xi). Следовательно, для любой вершины х фиксированного пути выполняется равенство d(x)=d(v0,x), в частности, d(v’)=d(v0,v’). Отсюда следует, что если существует (v0,v)–путь в сети N, то на момент завершения работы алгоритма выполняется равенство d(v)=d(v0,v).

Теорема доказана.

Итак, мы рассмотрели вопрос о нахождении самого короткого пути между двумя вершинами. Однако иногда возникают ситуации, когда надо найти самый длинный путь между данными вершинами. Рассмотрим одну из таких ситуаций.

Предположим, что надо выполнить некоторую совокупность работ. Известно время выполнения каждой работы. Для каждой работы указаны предшествующие работы (более точно – непосредственно предшествующие), т.е. те работы, без выполнения которых данная работа выполняться не может. Такую совокупность работ будем называть проектом.

В качестве примера рассмотрим проект, состоящий из семи работ v1,…,v7, время выполнения и предшественники которых указаны в таблице 2.

Таблица 2

  Проект удобно представить в виде ориентированного графа, вершинами которого являются работы, а дуги вводятся следующим образом: если работа х предшествует работе y, то изображается (x,y)–дуга. Над такой дугой проставляется время выполнения работы y. Будем считать, что полученная сеть не содержит контуров. В таком случае, сеть имеет хотя бы один источник и хотя бы один сток. Нам будет удобно, чтобы сеть имела в точности один источник и в точности один сток. Для этого расширим проект, добавив две «фиктивные» работы: «начало проекта» и «завершение проекта». Первая работа предшествует всем источникам, а все стоки предшествуют второй из добавленных работ. Время выполнения этих работ равно нулю. Полученная расширенная сеть называется сетевым графиком проекта. Сетевой график проекта, представленного таблицей 2, изображен на рис. 2. Фиктивные работы – v0 и v8.

Рис. 2

Поскольку сетевой график не содержит контуров, то в силу теоремы 2 можно считать, что вершины сетевого графика занумерованы так, что если vi предшествует vj, то i<j.

Рассмотрим две задачи, связанные с сетевыми графиками.

Первая задача – определить, каково наименьшее время, необходимое для выполнения всего проекта.

Введем ряд обозначений. Время выполнения работы v будем обозначать через t(v), а наименьшее время выполнения всего проекта через Tmin. Пусть, далее, PBH(v) и PBO(v) – наиболее раннее время начала и, соответственно, наиболее раннее время окончания работы v. Источник сетевого графика будем обозначать через v0, сток – через vk. Таким образом, Tmin=PBH(vk)=PBO(vk). Следующее утверждение очевидно.

Предложение 1. Для любой вершины v¹v0 сетевого графика справедливы равенства

Используя это предложение, несложно вычислить величины PBH(v) и PBO(v) для всех вершин v сетевого графика. Напомним, что вершины сетевого графика занумерованы так, что если vi предшествует vj, то i<j. Полагаем, что PBH(v0)=PBO(v0)=0. Пусть, далее, указанные величины найдены для всех вершин v0,v1,…,vl-1. Тогда поскольку все вершины, предшествующие vl, находятся среди v0,v1,…,vl-1, то полагаем PBH(vl)=max{PBO(v’)½v’ предшествует vl} и PBO(vl)=PBH(vl)+t(vl). Результат вычисления для сетевого графика, изображенного на рис. 6.13 , приведен в таблице 6.3. Мы видим, что в этом случае Tmin=12.

Таблица 3

Как показывает следующее утверждение, наиболее раннее время выполнения проекта равно длине самого длинного пути из v0 в vk.

Теорема 6.7. Наиболее раннее время окончания работы v равно длине самого длинного пути из v0 в v.

Доказательство. Для v=v0 теорема очевидна. Предположим, что теорема доказана для вершин v0,v1,…,vl-1 и v=vl. Пусть, далее, среди вершин v’, предшествующих вершине v, максимум величины PBO(v’) достигается на вершине vi. Тогда PBH(v)=PBO(vi) и PBO(v)=PBO(vi)+t(v). Это означает, что существует путь из v0 в v, имеющий длину PBO(v). Рассмотрим произвольный путь из v0 в v, обозначим его длину через d.Этот путь должен проходить через одну из вершин, предшествующих v. Пусть он проходит через вершину vj (см. рис. 3).

Рис. 3

Поскольку для vj утверждение теоремы справедливо, то d(PBO(vj)+t(v). Но в силу введенных выше обозначений, справедливо неравенство PBO(vi)(PBO(vi). Это означает, что d(PBO(vi)+t(v)=PBO(v).

Теорема доказана.

Заметим, что самый длинный путь из v0 в vk может быть не один (см. рис. 2).

Вторая задача, связанная с сетевыми графиками состоит в нахождении так называемых критических работ. Предположим, что уже вычислено наиболее раннее время окончания каждой работы и всего проекта в целом. Тогда возникает вопрос о нахождении самого позднего времени окончания работ, которое не влияет на время выполнения всего проекта в целом. Введем соответствующие обозначения. Пусть задано время Т выполнения проекта в целом. Ясно, что T³Tmin. Через ПВН(v) и ПВO(v) обозначим соответственно наиболее позднее время начала и наиболее позднее время окончания работы v, не ведущие к увеличению времени Т выполнения проекта. Работа v, для которой PBO(v)=ПВО(v), называется критической. Временному графику выполнения критических работ руководитель проекта должен уделять особое внимание, поскольку сдвиг во времени при выполнении этих работ повлечет увеличение времени выполнения всего проекта в целом.

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

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

Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначен их вес – длина пути. Рядом с каждой вершиной красным обозначена метка – длина кратчайшего пути в эту вершину из вершины 1.

Инициализация

Метка самой вершины 1 полагается равной 0, метки остальных вершин – недостижимо большое число (в идеале - бесконечность). Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

Первый шаг

Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди.

Первый сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2 (10000), поэтому новая метка 2-й вершины равна 7.

Аналогично находим длины пути для всех других соседей (вершины 3 и 6).

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная.

Второй шаг

Шаг 1 алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Вершина 1 уже посещена. Следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а 9 < 17, поэтому метка не меняется.

Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна 22 (7 + 15 = 22). Поскольку 22<10000, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, помечаем её как посещенную.

Третий шаг

Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим следующие результаты.

Четвертый шаг

Пятый шаг

Шестой шаг

Таким образом, кратчайшим путем из вершины 1 в вершину 5 будет путь через вершины 1 - 3 - 6 - 5, поскольку таким путем мы набираем минимальный вес, равный 20.

 

Реализация алгоритма Дейкстры

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

Теперь все готово для написания кода

Пример реализации для 1С можно посмотреть тут "Реализация алгоритма поиска кратчайшего пути средствами 1С"