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

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

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

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

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

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

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

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

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

c_ij = l (х_i, х_j), если (х_i, х_j) € X;

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

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

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

1? j? n.

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

1? j? n.

Используя утверждение 1, нетрудно описать алгоритм нахождения таблицы значении величин л_i^(k) (будем записывать в виде матрицы, где i — номер строки, k+1 — номер столбца). Действительно, используя рекуррентные соотношения (2), (3) и исходя из (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). Отметим, однако, что теперь могут существовать вершины, достижимые из х₁ с длинами минимальных путей из х₁ в эти вершины, равными ?, т. е. мы уже не можем судить по л_i^(n-1) о достижимости вершин х_i из х₁.

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

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

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

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

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

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

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

л_i3^(k1−2) + с_i3,i2 = л_i1^{(k1 — 1)}

^{.. .. .. .. .. .. ... .} (4).

л_i⁽⁰⁾ + c_{i j} = л_i⁽¹⁾

^{k1+1 k1+1 k1 k1}

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

Из (4) с учетом того, что л_i1^(k1)=л_i1^{(n — 1)} < ?, имеем c_{i2, i1} i, _i < ?, л_i⁽⁰⁾ < ?,.

^{k1+1 k1 k1+1}

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

(х_i2, х_i1), …, (х_i, х_i) € X, l (х_i2, х_i1) = c_{i2, i1}, …, l (х_i2, х_i1) = c_{i, I};

^{k1+1 k1 k1+1 k1 k1+1 k1}

л_i⁽⁰⁾ = 0, i = 1, х_i = х₁ (5).

^{k1+1 k1+1 k1+1}

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

l (х_1k1 х_i … х_i2 х_i1) = л_i1^(k1), (6).

т. е. х₁ х_i … х_i2 х_i1 — исходный минимальный путь из х₁ в х_i1 в нагруженном орграфе D. Заметим, что в этом пути ровно k_i дуг. Следовательно мы определили путь с минимальным числом дуг среди всех минимальных путей из х₁ в х_i1 в нагруженном орграфе D.

Замечание 4. Номера i₂, i₃, …, i_k1, удовлетворяющие (6), вообще говоря, могут быть выделены неоднозначно. Эта неоднозначность соответствует случаям, когда существует несколько различных путей из х₁ в х_i1 c минимальным числом дуг среди минимальных путей из х₁ в х_i1 в нагруженном орграфе D.

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

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

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