Выбор алгоритма. 
Алгоритмы теории графов: алгоритм Форда–Беллмана

Для решения поставленной задачи будем использовать алгоритм Форда — Бэллмана.

Назовем орграф D = (V, X) нагруженным, если на множестве дуг X определена некоторая функция l: X > R, которую часто называют весовой функцией. Тем самым в нагруженном орграфе D в каждой дуге x € X поставлено в соответствие некоторое действительное число l (x). Значение l (x) будем называть длинной дуги x. Для этого пути р нагруженного орграфа D обозначим через l (р) сумму длин входящих в р дуг, при этом каждая дуга учитывается столько раз, сколько она входит в путь. Величину l (р) будем называть длинной пути р в нагруженном орграфе D. Ранее так называлось количество дуг в пути р. В связи с этим заметим, что если длины дуг выбраны равными l, то l (р) выражает введенную ранее длину пути р в ненагруженном орграфе. Следовательно, любой ненагруженный орграф можно считать нагруженным с длинами дуг, равными l. Аналогично определяется и нагруженный граф, а также длина маршрута в нем.

Пусть в нагруженном орграфе D из вершины х в вершину щ, где х? щ, называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из х в щ. Аналогично определяется и минимальный маршрут в нагруженном графе G.

Если в нагруженном орграфе D имеются замкнутые пути отрицательной длины, то для заданных вершин х1, щ орграфа D, где х? щ, минимального пути из х в щ может и не быть. Действительно, если в D имеется замкнутый путь у отрицательной длины и существует путь из х в щ, проходящий хотя бы через одну вершину, содержащуюся в у, то очевидно, что в D найдется путь р из х в щ вида р = р1П у П р2, где р1, р2 — пути в D (возможно также, что-либо р1, либо р2 является пустой последовательностью; при этом предполагаем, что Ш П у = у П Ш = у). Но тогда р1 П у П у П р2, р1 П у П у П у П р2 … также пути в D из х в щ, и длина каждого следующего пути в этой последовательности отличается от длины предыдущего на l (у) < 0, а значит, длины путей из х в щ могут принимать сколь угодно малые отрицательные значения. Аналогичная ситуация имеет место в случае, когда в нагруженном графе G вершины х, щ находятся в одной компоненте связности, содержащей хотя бы одно ребро отрицательной длины. В таких случаях имеют смысл лишь задачи поиска минимальных путей (маршрутов) среди путей (маршрутов), число дуг (ребер) в которых ограничено сверху.

Приведем некоторые свойства минимальных путей (маршрутов) в нагруженном орграфе D = (V, X) (графе G = (V, X)):

• 1) если существует x € X l (x) > 0, то любой минимальный путь (маршрут) является простой цепью;
• 2) если х1×2 … хk — минимальный путь (маршрут), то для любых номеров i, j таких, что 1? i < j? k, путь (маршрут) хi хi+1 также является минимальным;
• 3) если х … и щ — минимальный путь (маршрут) среди путей из х в щ (среди маршрутов, соединяющих х, щ), содержащих не более k+1 дуг (ребер), то х … u — минимальный путь (маршрут) среди путей из х в u (среди маршрутов, соединяющих х, u), содержащих не более k дуг (ребер).

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

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

Пусть D = (V, X) — нагруженный орграф, V = { х1, …, хn}, n > 2. Введем величины лi (k), где i = 1, …, n, k = 1, 2, …. Для каждых фиксированных i и k величина лi (k) равна длине минимального пути среди путей из х1 в хi, содержащих не более k дуг; если же таких путей нет, то лi (k) = ?. Кроме того, если произвольную вершину х Ђ V считать путем из х в х нулевой длины, то величины лi (k) можно ввести также и для k = 0, при этом л1(0) = 0, лi (0) = ?, i = 2, …, n. (1).

Введем также в рассмотрение квадратную матрицу C (D) = [сij] порядка n с элементами.

cij = l (хi, хj), если (хi, хj) € X;

?, если (хi, хj) € Х, которую будем называть матрицей длин дуг нагруженного орграфа D.

Следующее утверждение дает простые формулы дл вычисления величин лi (k).

Утверждение 1. При i — 2, …, n, k? 0 выполняется равенство лi (k+1) = min {лj (k)+cij}.

1? j? n.

а при i — 1, k? 0 справедливо равенство лi (k+1) = min{0; min {лj (k)=cj1}}.

1? j? n.

Используя утверждение 1, нетрудно описать алгоритм нахождения таблицы значении величин лi (k) (будем записывать в виде матрицы, где i — номер строки, k+1 — номер столбца). Действительно, используя рекуррентные соотношения (2), (3) и исходя из (1), последовательно определяем набор величин л1(k), …, лn (k) ((k+1) столбец матрицы), начиная с k = 0, а затем шаг за шагом увеличивая значение k до любой необходимой величины.

Будем теперь предполагать, что в D отсутствуют простые контуры отрицательной длины (ниже в утверждении 5 приводится простой метод проверки этого условия). Для дальнейших рассуждений нам понадобятся дополнительные утверждения.

Утверждение 2. Из всякого замкнутого пути отрицательной длины можно выделить простой контур отрицательной длины.

Утверждение 3. Если в нагруженном орграфе отсутствуют простые контуры отрицательной длины, то в нем нет замкнутых путей отрицательной длины.

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

Замечание 2. При определении нагруженного графа мы предполагали, что величины l (x), x € X, конечны. Между тем величины лi (k) (i = 1, 2, …, n, k = 0, 1, …, n — 1) можно аналогичным образом определить и для случая, когда для некоторых x € X выполняется l (x) = ?. При этом сохраняет силу утверждение 1, а следовательно, и алгоритм построения таблицы величин лi (k). Отметим, однако, что теперь могут существовать вершины, достижимые из х1 с длинами минимальных путей из х1 в эти вершины, равными ?, т. е. мы уже не можем судить по лi (n-1) о достижимости вершин хi из х1.

Замечание 3. Если при некотором k0, где 0? k0? n — 2, выполняются равенства лi (k0) = лi (k0 + 1), i = 1, 2, …, n, и, в частности, лi (n — 1) = лi (k0), i = 1, 2, …, n, т. е. в данном случае значения лi (k) при k > k0 не несут никакой дополнительной информации, и тогда имеет смысл оборвать процесс последовательного определения наборов величин л1(k), …, лn (k) на значении k = k0.

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

Утверждение 5. Пусть в орграфе D = (V, X), где V = { х1, …, хn}, любая вершина хi, i € {2, …, n}, достижима из х1. Тогда, для того чтобы в D отсутствовали простые контуры отрицательной длины, необходимо и достаточно, чтобы выполнялось условие лi (n -1) = лi (n), i = 1, …, n.

Алгоритм (алгоритм Форда — Беллмана) нахождения минимального пути в нагруженном орграфе D из х1 в хi1, (i? 1):

Шаг 1. Пусть мы уже составили таблицу величин лi (k), i = 1, 2, …, n, k = 0, 1, 2, …, n — 1. Если лi (n-1) = ?, то вершина хi1 не достижима из х1 (предполагаем, что все величины l (x), x € X конечны). В этом случае работа алгоритма заканчивается.

Шаг 2. Пусть лi1(n-1) < ?, тогда число лi1(n-1) выражает длину любого минимального пути из х1 в хi1 в нагруженном орграфе D. Определим минимальное число k? 1, при котором выполняется равенство лi1(k1) = лi1(n-1). По определению чисел лi (k) получаем, что k1 — минимальное число дуг в пути среди всех минимальных путей х1 в хi1 в нагруженном орграфе D.

Шаг 3. Последовательно определяем номера i2, …, ik1+1 такие, что лi2(k1−1) + сi2, i1 = лi1(k1).

лi3(k1−2) + сi3, i2 = лi1(k1 — 1).

лi (0) + ci j = лi (1).

k1+1 k1+1 k1 k1.

(эти номера найдутся в силу (2)).

Из (4) с учетом того, что лi1(k1)=лi1(n — 1) < ?, имеем ci2, i1.

k1+1 k1 k1+1.

откуда, используя (1), получаем.

• (хi2, хi1), …, (хi, хi) € X, l (хi2, хi1) = ci2, i1, …, l (хi2, хi1) = ci, I;
• 1+1 k1 k1+1 k1 k1+1 k1

лi (0) = 0, i = 1, хi = х1 (5).

k1+1 k1+1 k1+1.

Складывая равенства (4) и учитывая (5), имеем.

l (х1k1 хi … хi2 хi1) = лi1(k1),.

т. е. х1 хi … хi2 хi1 — исходный минимальный путь из х1 в хi1 в нагруженном орграфе D. Заметим, что в этом пути ровно ki дуг. Следовательно мы определили путь с минимальным числом дуг среди всех минимальных путей из х1 в хi1 в нагруженном орграфе D.

Замечание 4. Номера i2, i3, …, ik1, удовлетворяющие (6), вообще говоря, могут быть выделены неоднозначно. Эта неоднозначность соответствует случаям, когда существует несколько различных путей из х1 в хi1 c минимальным числом дуг среди минимальных путей из х1 в хi1 в нагруженном орграфе D.

Замечание 5. Алгоритм можно модифицировать, с тем х1 в хi1, содержащих не более k0 дуг, где k0 — заданное число, k0 > 1. Xтобы определить минимальный путь из х1 в заданную вершину хi1 среди путей из х1 в хi1. Для этого в алгоритме вместо лi (n — 1) следует воспользоваться лi1(k0). Отметим, что при использовании указанной модификации алгоритма предположение об отсутствии простых контуров отрицательной длины излишне. При том, если в орграфе D имеются простые контуры отрицательной длины, может выполняться неравенство л1(k0) < 0.

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

Замечание 7. Нетрудно доказать, что утверждение 1, а следовательно, и алгоритм вместе с его модификацией останутся справедливыми и для нагруженного ориентированного псевдографа. При этом в случае кратных дуг следует учитывать лишь дуги минимальной длины, а при наличии петель — лишь, петли отрицательной длины. Это замечание переносится и на неориентированные псевдографы.