Рис. 25.1 25.1 Ориентированный граф с рёбрами отрицательного веса. У каждой вершины указан вес кратчайшего пути из s в эту вершину. Поскольку вершины ей/ образуют цикл отрицательного веса, достижимый из вершины s, веса кратчайших путей в каждую из этих вершин равны -оо. Сделав несколько циклов, можно пойти в д, так что вес кратчайшего пути в д также равен - оо. Вершины h, г и j недостижимы из s, так что (хоть они и лежат на цикле отрицательного веса), вес кратчайшего пути в эти вершины есть оо.

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

Представление кратчайших путей в алгоритме

Часто требуется не просто подсчитать веса кратчайших путей, но и найти сами эти пути. Мы будем использовать для их представления тот же приём, что и в деревьях поиска в ширину в разд. 23.2. Именно, пусть G = (V, Е) - заданный граф. Для каждой вершины v G V мы будем помнить её предшественника (predecessor) ir[v]. Предшественник вершины - это либо другая вершина (указатель на неё), либо nil. По завершении работы алгоритмов, рассматриваемых в этой главе, цепочка предшественников, начинающаяся с произвольной вершины v, будет представлять собой кратчайший путь из s в v (в обратном порядке), так что, если ir[v] ф nil, процедура Print-Path(G, s, v) из разд. 23.2 напечатает кратчайший путь из s в v.

В процессе работы алгоритмов цепочки, получаемые итерациями 7г, не обязательно будут кратчайшими путями, но всё равно можно рассмотреть ориентированный подграф предшествования (predecessor subgraph) Gv = (VV,EV), определённый так: вершины Gv - это те вершины G, у которых предшественник отличен от nil, плюс исходная вершина:

Vw = { v е V : tt[v] ф nil } U {s}.

Рёбра Gv - это стрелки, указывающие из ir[v] ф nil в v.

Ev = {(tt[v],v) е Е : v eVv\{s}}.

Мы докажем, что по окончании работы наших алгоритмов граф Gv будет «деревом кратчайших путей» - деревом с корнем s, содержащим кратчайшие пути из s во все достижимые из s вершины. Деревья кратчайших путей аналогичны деревьям поиска в ширину из разд. 23.2, с той разницей, что на сей раз кратчайшими объявляются пути с наименьшим весом, а не наименьшим числом ребер.

Рис. 25.2 25.2 (а) Взвешенный ориентированный граф; в вершинах указаны веса кратчайших путей из s. (б) Серые рёбра образуют дерево кратчайших путей с корнем s. (в) Другое дерево кратчайших путей с тем же корнем.

Точное определение выглядит так. Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w: Е -> Ж. Предположим, что G не имеет циклов отрицательного веса, достижимых из исходной вершины s, так что все кратчайшие пути из s корректно определены. По определению, дерево кратчайших путей (shorted-paths tree) с корнем в s есть ориентированный подграф G = (V, Е), где V С V и Е С Е, для которого:

1.V - множество вершин, достижимых из вершины v;

2.G является деревом с корнем s;

3.для каждого v £ V путь из s в v в графе G является кратчайшим путем из s в v в графе G.

Ни кратчайшие пути, ни деревья кратчайших путей не обязаны быть единственными. На рис. 25.2 изображен взвешенный ориентированный граф и два различных дерева кратчайших путей с общим корнем. План главы

Все алгоритмы для поиска кратчайших путей, рассматриваемые в этой главе, основаны на технике, известной под названием релаксация (relaxation). В разд. 25.1 мы рассматриваем общие свойства кратчайших путей, а затем доказываем ряд важных фактов про релаксацию. Алгоритм Дейкстры, решающий задачу о кратчайших путях из одной вершины для случая неотрицательных весов, разобран в разд. 25.2. Разд. 25.3 посвящен алгоритму Беллмана-Форда, применимому и в том случае, когда рёбра могут иметь отрицательный вес. (Если граф содержит цикл отрицательного веса, достижимый из исходной вершины, алгоритм Беллмана-Форда сообщает об этом.) В разд. 25.4 рассматривается алгоритм для нахождения кратчайших путей в ациклических графах, работающий за линейное время. Наконец, в разд. 25.5 мы показываем, как применить алгоритм Беллмана-Форда к решению одного специального случая задачи линейного программирования.

При работе с символами оо и -оо мы будем придерживаться следующих соглашений. Если а ф -оо, то будем считать, что а + оо = оо + а = оо; аналогично, если а ф оо, то а+( -оо) = ( - оо)+а = - оо.

25.1. Кратчайшие пути и релаксация

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

При первом чтении вы можете разобрать только формулировки результатов (обратите особое внимание на лемму 25.7; леммы 25.8 и 25.9 при первом чтении можно пропустить), после чего перейти к алгоритмам разд. 25.2 и 25.3.

Свойство оптимальности для подзадач

Любая часть кратчайшего пути сама есть кратчайший путь. Это значит, что задача о кратчайших путях обладает свойством оптимальности для подзадач - признак того, что к ней может быть применимо динамическое программирование (глава 16) или жадный алгоритм (глава 17). И действительно, алгоритм Дейкстры является жадным алгоритмом, а алгоритм Флойда-Уоршолла для нахождения кратчайших путей между всеми парами вершин (глава 26) основан на динамическом программировании. Следующая лемма и ее следствие уточняют, в чем конкретно состоит свойство оптимальности для подзадач в задаче о кратчайших путях.

Лемма 25.1 (Отрезки кратчайших путей являются кратчайши-

Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w: Е -> Ж. Если р = (v\, v2, , vk) - кратчайший путь из vi в vk и 1 г j к, то рг] = (vi,vi+1,...,Vj) есть кратчайший путь из V{ в Vj.

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

Если путь pij не кратчайший, то, заменяя в пути р участок от Vi до Vj на более короткий путь из иг- в Vj, мы уменьшим вес пути из pi в рк - противоречие. (Здесь «более короткий» означает «с меньшим весом».)

Следствие из доказанной леммы обобщает лемму 23.1.

Следствие 25.2

Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w: Е -> R. Рассммотрим кратчайший путь р из s

в v. Пусть и -т- v - последнее ребро этого пути (р есть s и -> v). Тогда S(s, v) = S(s, и) + w(u, v). Доказательство

По лемме 25.1 путь р является кратчайшим, так что S(s,v) = w(p) + w(u, v) = S(s, и) + w(u, v).

Следующая лемма проста, но полезна.

Лемма 25.3 Пусть G = (V, Е) - взвешенный ориентированный