Данная функция находит подходящее ребро минимальной приведенной стоимости. Это простая реализация производит обход всех ребер в сети.

int costR(Edge *e, int v)

{ int R * e-> cost() + phi[e-> w()] - phi[e-> v()];

return e-> from(v)? R: -R; } Edge *besteligible() { Edge *x = 0;

for (int v = 0, min = C*G.V(); v < G.V(); v++) {

typename Graph:: adjIterator A(G, v); for (Edge* e = A.beg();! A.end(); e = A.nxt()) if (e-> capRto(e-> other(v)) > 0) if (e-> capRto(v) == 0) if (costR(e, v) < min)

{ x = в; min = costR(e, v); } }

return x; }

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

Глава 22, Потоки в сетях

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

Таблица 22.14. Сетевой симплексный алгоритм (базовая реализация)

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

template < class Graph, class Edge> class MINCOST { const Graph & G; int s, t; int valid;

vector< Edge *> st; vector< int> mark, phi; void dfsR(Edge); int ST(int); int phiR(int);

int lсa(int, int); Edge *augment(Edge *); bool onpath(int, int, int); void reverse(int, int); void update (Edge *, Edge *);

int costR(Edge *, int); Edge *besteligible(); public:

MINCOST(Graph & G, int s, int t): G(G), s(s), t(t)

st(G.V()), marfc(G.V(), -1), phi(G.V()) {

Edge *z = new EDGE(s, t, M*G.V(), C*G.V()); G.insert(z);

z-> addflowto(t, z-> cap()); dfsR(z);

for (valid = 1;; valid++) {

phi[t] = z-> costRto(s); mark[t] = valid; for (int v = 0; v < G.V(); v++)

if (v! = t) phi[v] = phiR(v); Edge *x = besteligible(); if (costR(x, x-> v()) == 0) break; update(augment(x), x); }

G.remove(z); delete z; }

Производительность в худшем случае, характерном для программы 22.14, по меньшей мере, в V раз меньше, чем аналогичный параметр для реализации с вычеркиванием цик­лов, представленной программой 22.9, поскольку затраты времени на один цикл состав­ляют Е (чтобы найти подходящее ребро), а не VE (чтобы отыскать отрицательный цикл). И хотя есть подозрение, что применение максимального наращивания приведет к мень­шему числу операций наращивания, чем для случая, когда берется первый попавшийся отрицательный цикл, как это имеет место в условиях алгоритма Беллмана-Форда, тем не менее, как удалось показать, это подозрение лишено оснований. Конкретные ограниче-

Часть 5. Алгоритмы на графах