Кратчайшие пути

Рассмотрим орграф со взвешенными дугами и путь из вершины i в вершину j в этом графе. Сумма весов дуг этого пути называется его длиной. Путь минимальной длины из i в j называется кратчайшим путем из i в j.

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

Рассмотрим орграф G = (V, A) с выделенной вершиной s и весами wij, (i, j) ∈ A. Алго-

ритм присваивает вершинам временные и постоянные метки. Постоянная метка вершины

равна длине кратчайшего пути из s в эту вершину. Кроме того, формируется массив P red, в котором P red (v) содержит номер непосредственного предшественника вершины v в кратчайшем пути из s в v. Таким образом s,..., P red (P red (v)), P red (v), v является кратчайшим путем из s в v.

Алгоритм Дейкстры (построения кратчайших путей из вершины s во все остальные вершины орграфа в случае неотрицательных весов дуг)

Шаг 1. (Начало). Помечаем вершину s постоянной меткой Length (s) = 0. Все осталь- ные вершины v / = s помечаются временными метками Length (v) = ∞. Полагаем номер

итерации i = 1 и номер текущей вершины, помеченной постоянной меткой, u = s.

Шаг 2. (Рекурсия). Полагаем i = i +1. Рассмотрим вершину u. Для всех ее непосредствен- ных последователей v с временной меткой вычисляем M = min {Length (v), Length (u) + wuv}. Если M меньше временной метки Length (v), то вычисляем новую метку Length (v) =

M и полагаем P red (v) = u.

Далее среди всех вершин с временными метками выбираем вершину k с наименьшей мет- кой и делаем ее постоянной. Если i < n − 1, то полагаем u = k и повторяем Шаг 2. Иначе

стоп: все кратчайшие пути из s в остальные вершины могут быть восстановлены по мас- сиву Pred.

Алгоритм построения кратчайших путей между всеми парами вершин и проверки наличия цикла отрицательного веса (дополнительный материал). Приводимый ниже алгоритм предложен Флойдом.

Рассмотрим орграф G = (V, A). Пусть W 0 = ||wij || – n ×n матрица весов дуг этого графа. Полагаем wij =

∞, если дуга (i, j) отсутствует, и wii = 0 для всех i ∈ V. Алгоритм Флойда строит последовательность

ij

матриц W 1, W 2 ,..., W n такую, что элемент wn

матрицы W n равен длине кратчайшего пути из i в j в

графе G. Матрица W k определяется по матрице W k− 1:

wk k− 1

k− 1

k− 1

ij = min {wij, wik + wkj }. (1)

ij

Пусть P k – кратчайший путь из i в j с внутренними вершинами из множества { 1, 2 ,..., k}. Справедлива

ij

Теорема5 Для 0 ≤ k ≤ n, величина wk

является длиной пути P k.

ij

В алгоритме Флойда одновременно с длинами кратчайших путей отыскиваются сами пути с помощью

ij

матриц Z 0, Z 1 ,..., Zn, где элемент zk

матрицы Z k указывает на вершину, непосредственно следующую

ij

за i в P k. Тогда ясно, что

z 0

ij =

ij

(j, если w 0

ij

0, если w 0

/ = ∞,

= ∞.

Матрица Z k получается из Z k− 1следующим образом. Пусть M = min {wk− 1, wk− 1+ wk− 1 }. Тогда

(zk− 1

k− 1

ij ik kj

zk ij, если M = wij,

ij =

zk− 1

k− 1

ik, если M < wij.

Если M = wk− 1, то длина пути P k равна длине пути P k− 1. Иначе P k получается в результате склеивания

ij

путей P k− 1 и P k− 1 и zk

ij

= zk− 1.

ij ij

ik kj

ij ik

Очевидно, что кратчайший путь из i в j определяется последовательностью вершин i, i 1, i 2 ,..., ip, j,где

i 1= zn, i 2= zn

, i 3= zn

,..., j = zn.

ij i 1 j

i 2 j

ipj

Отметим, что в (1) если wk− 1или wk− 1равно ∞, то wk

= wk− 1.

ik kj

ij ij

Алгоритм Флойда (построения кратчайших путей между всеми парами вершин и проверки наличия

цикла отрицательного веса)

(В процессе вычислений матрицу W k записываем на место W k− 1, а матрицу Z k – на место Z k− 1, k =

1 ,..., n. Таким образом, используем одно и то же обозначение W для всех W k и Z для всех Z k.)

Шаг 1. (Начало). Полагаем k = 0. Строим матрицы W = W 0 и Z = Z 0.

Шаг 2. (Рекурсия). Полагаем k = k + 1. Для всех таких вершин i / = k, что wik / = ∞ и всех таких вершин

j / = k, что wkj/ = ∞, вычисляем M = min {wij, wik + wkj}. Если M < wij, то полагаем zij = zik и wij = M.

Если появляется wii< 0, то стоп: вершина i принадлежит некоторому циклу отрицательного веса.

Если все wii ≥ 0 и k = n, то стоп: wij – длины всех кратчайших путей, а zij – первая после i вершина в

кратчайшем пути из i в j.

Если все wii≥ 0 и k < n, то повторяем Шаг 2.

Сетевое планирование и управление проектами

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

Примерами таких проектов могут быть

– строительство большого объекта,

– разработка комплекса компьютерных программ,

– производство самолета, ракеты или другого большого изделия,

– выпуск нового продукта,

– передислокация фирмы или производства.

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

Наиболее распространенными методами планирования и управления проектами являются

сетевые методы.

Сетевая модель проекта включает следующее:

а) Элементарные работы (иногда называемые требованиями или операциями), которые должны быть проведены для выполнения проекта.

б) Связи между элементарными работами в виде сети, в которой вершины и дуги пред- ставляют собой связи между элементарными работами. При этом будет присутствовать начальная, возможно фиктивная, работа, соответствующая началу проекта, и конечная работа, соответствующая его завершению.

Сетевые методы включают следующее:

а) Определение или оценивание длительности pj выполнения каждой элементарной рабо- ты j.

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

в) Использование знания критического пути для получения более экономичного и эффек- тивного расписания.

Полученная сеть и расписание могут использоваться для контроля выполнения проекта путем внесения изменений, соответствующих реальным данным.

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

Отношения предшествования отражаются в сетевой модели проекта.

Наиболее распространены два типа сетевых моделей, называемые 1) действие-на-вершине

и 2) действие-на-дуге.

В модели 1) вершины представляют собой элементарные работы проекта, а дуги указыва- ют последовательность их выполнения. Вершинам приписаны длительности выполнения соответствующих работ.

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

Рассмотрим модель 2) ”действие-на-дуге”. Как уже отмечалось, длительность выполне- ния проекта определяется длиной критического пути. Проект не может быть выполнен быстрее, чем длина критического (самого длинного) пути.

Алгоритм отыскания критического пути (применяется для отыскания критического пути между выделенными вершинами s и t ацикличного орграфа G = (V, A) с неотрица-

тельными весами дуг pij, (i, j) ∈ A.)

Метка вершины Length (v) соответствует длине самого длинного пути из s в v.

Шаг 1. (Начало). Помечаем вершину s меткой Length (s) = 0. Полагаем множество по- меченных вершин S = {s}.

Шаг 2. (Рекурсия). Находим непомеченную вершину v, в которую входят дуги толь-

v

ко из помеченных вершин (все вершины множества B 0

помечены). Помечаем v меткой

v

Length (v) = max {Length (u) + puv|u∈ B 0 } и включаем v в S. Если максимум достигается

0 0 0

на вершине u

∈ Bv, то самый длинный путь в вершину v пришел из вершины u.

Если помечена вершина t, то стоп: длина критического пути (длительность выполнения

проекта) равна Length (t) и сам путь может быть восстановлен с помощью поиска с воз- вратом. Иначе повторяем Шаг 2.

После того, как критический путь построен, для каждой работы j могут быть вычислены наиболее ранний ESj и наиболее поздний LSj моменты ее начала такие, что начало работы в промежутке [ ESj, LSj ] не приводит к увеличению длительности всего проекта. Начало работы ранее ESj невозможно из-за ограничений предшествования, а ее начало после LSj приведет к увеличению длительности проекта.

Знание указанных моментов позволяет реализовать расписание более гибко, поскольку есть возможность задержки начала выполнения некоторых работ без ущерба для дли- тельности выполнения всего проекта.

Наиболее ранние моменты начала работ ESj равны меткам соответствующих вершин в приведенном выше алгоритме.

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

LSi = min {LSj− p (ij) |j∈ A 0, все вершины A 0 помечены }.

i i

Значение LSi равно T минус длина наиболее длинного пути из вершины i в вершину t.

Дата добавления: 2015-07-08