графе могут быть рёбра с отрицательным весом.)

25-3.6 Пусть взвешенный ориентированный граф G = (V, Е) имеет цикл отрицательного веса. Разработайте алгоритм, печатающий вершины такого цикла (хотя бы одного).

25.3. Кратчайшие пути в ациклическом ориентированном графе

В ациклическом ориентированном графе G = (V, Е) кратчайшие пути из одной вершины можно найти за время 0(V + Е), если проводить релаксацию ребер в порядке, заданном топологическим упорядочением вершин. Заметим, что в ациклическом ориентированном графе кратчайшие пути всегда определены, поскольку циклов отрицательного веса (и вообще циклов) нет.

В разделе 23.4 мы рассматривали алгоритм топологической сортировки вершин ациклического графа. Он располагает их в таком порядке, чтобы все рёбра графа вели от «меньших» вершин к «большим» (в смысле этого порядка). После этого мы просматриваем вершины в этом порядке и для каждой вершины подвергаем релаксации все выходящие из неё рёбра.

Dag-Shortest-Paths(G,w,s)

1топологически отсортировать вершины G

2Initialize-Single-Source(G,s)

3for (для) всех вершин и (в найденном порядке)

4do for (для) всех вершин v \in Adj[u]

5do Relax(u,v,w)

Пример работы этого алгоритма приведён на рис. 25.8.

Оценим время работы алгоритма Dag-Shortest-Paths. Как мы видели в разд. 23.4, стоимость топологической сортировки (строка 1) есть Q(V + Е), а стоимость инициализации в строке 2 есть 0(V). В цикле в строках 3-5 каждое ребро обрабатывается, как и в алгоритме Дейкстры, ровно один раз, но, в отличие от алгоритма Дейкстры, стоимость такой обработки есть 0(1). Стало быть, наш алгоритм выполняется за время Q(V + Е), пропорциональное

Рис. 25.8 (в оригинале в подписи была опечатка: v, тогда как надо и).

Рис. 25.8 25.8. Алгоритм для поиска кратчайших путей в ациклическом ориентированном графе. Вершины топологически отсортированы (на рисунке слева направо). Исходная вершина - s. В вершинах записаны значения функции d; для серых рёбер (u, v) имеем n[v] = и. (а) Перед первой итерацией цикла в строках 3-5. (б-ж) Последовательные состояния после каждой итерации цикла в строках 3-5. На каждом из этих рисунков прибавляется по одной чёрной вершине (которая была вершиной и во время соответствующей итерации цикла). Значения d на рисунке (ж) - окончательные.

объему памяти, необходимому на представление графа с помощью списков смежных вершин.

Покажем, что алгоритм Dag-Shortest-Paths правилен.

Теорема 25.15

Пусть взвешенный ориентированный граф G = (V, Е) с исходной вершиной s не содержит циклов. Тогда по окончании работы процедуры Dag-Shortest-Paths для всех в £ У будут выполнены равенства d[v] = S(s,v), а подграф предшественников Gv будет деревом кратчайших путей.

Доказательство

Согласно лемме 25.9, достаточно доказать равенства d[v] = S(s,v). Если вершина v недостижима из s, то d[v] = S(s,v) = оо по следствию 25.6. Пусть теперь вершина v достижима из s и р = (s = vo, v\,..., Vk = v) - кратчайший путь. После топологической сортировки вершины этого пути расположены как раз в указанном порядке, так что ребро, (г>о, v±) подвергалось релаксации до ребра (t>i,t>2), которое предшествовало ребру (2,3) и т.д. Индукция по г с использованием леммы 25.7 (как в доказательстве корректности алгоритма Беллмана-Форда) показывает теперь, что d[vi\ = S(s,Vi) для всех г, что и требовалось доказать.

Интересное приложение описанного алгоритма - нахождение критических путей в смысле так называемой «технологии PERT» (program evaluation and review technique). В этом приложении каждое ребро ациклического ориентированного графа обозначает какое-то дело, а вес ребра есть время, необходимое на его выполнение. Если имеются рёбра (и, v) и (v, ж), то работа, соответствующая ребру (и, v), должна быть выполнена до начала работы, соответствующей ребру (v, ж). Критический путь (critical path) - это длиннейший путь в графе; его вес равен времени, которое будет затрачено на выполнение всех работ, если мы по максимуму используем возможность выполнять некоторые работы параллельно. Чтобы найти критический путь, можно поменять знак у всех весов на противоположный и запустить алгоритм Dag-Shortest-Paths.

Упражнения

25-4.1 Примените алгоритм Dag-Shortest-Paths к графу рис. 25.8, выбрав вершину г в качестве исходной.

25-4.2 Докажите, что алгоритм Dag-Shortest-Paths останется правильным, если обрабатывать только первые \V\ - 1 вершин.

25-4.3 В задаче о планировании работ по технологии PERT можно рисовать граф иначе, считая, что работы соответствуют не рёбрам, а вершинам графа. При этом каждой вершине присвоен вес (требуемое время), а стрелки указывают определяли последовательность работ (ребро (и, v) требует завершить работу и до начала работы v). Модифицируйте алгоритм Dag-Shortest-Paths так, чтобы он за линейное время находил в ациклическом ориентированном графе путь с максимальной суммой весов вершин.

25-4.4 Разработайте эффективный алгоритм, подсчитывающий общее число путей в ациклическом ориентированном графе, и оцените время его работы.

25.4. Ограничения на разности и кратчайшие пути

Общая задача линейного программирования состоит в отыскании экстремума линейной функции на множестве, заданном системой линейных неравенств. В этом разделе мы рассмотрим специальный случай задачи линейного программирования, сводящийся к нахождению кратчайших путей из одной вершины. Таким образом, рассматриваемый частный случай задачи линейного программирования может быть решён с помощью алгоритма Беллмана-Форда.

Линейное программирование

Общая задача линейного программирования (linear-programming problem) состоит в следующем. Даны т X га-матрица А, то-вектор Ь и га-вектор с. Требуется найти га-вектор ж, являющийся точкой максимума целевой функции (objective function) 2~Г=1 cixi на мно~ жестве, заданном т неравенствами, которые мы можем записать как Ах Ь.

Задачи линейного программирования часто возникают в приложениях, поэтому ими много занимались. На практике задачи линейного программирования быстро решаются с помощью симплекс-метода (simplex algorithm). Симплекс-метод основан на просмотре вершин многогранника, задаваемого неравенствами-ограничениями Ах Ь, при котором значение целевой функции увеличивается. (Симплекс-метод подробно описан в книге Данцига [53].)

Можно, однако, построить последовательность задач линейного программирования, для которой симплекс-метод будет требовать экспоненциального (от размера входа) времени. Метод эллипсоидов (ellipsoid algorithm) решает любую задачу линейного программирования за полиномиальное время, но на практике работает медленно. Существует также полиномиальный алгоритм Кармаркара (Karmarkars algoritm), сравнимый по практической эффективности с симплекс-методом.

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