Алгоритм 1.. Алгоритм 2.

⇐ ПредыдущаяСтр 3 из 5Следующая ⇒

Алгоритм 1.

begin

for vÎV do x(v):=0; {обнуление начального потока}

М1:

g(t):=¥ {достаточно большое число};

SPW(1):=t; C1:=1;C2:=1;{вершина t помечена и внесена в массив SPW}.

for i Î E \{t} do g(i):=0;{все вершины из Е\{t} не помечены}

M2:

i:=SPW(С1); {i-номер просматриваемой вершины}

for v Î V^-(i) do {пометка по прямым дугам}

begin j:=h2(v);

if g(j)=0 then {т.е. вершина j не помечена}

if (d(v) -x(v)) >0 then {по дуге можно пропустить дополнительный поток в прямом направлении}.

begin

g(j):=min (g(i) d(v) -x(v));

v(j):=v;

C2:= C2+1; SPW(C2):=j;

if j=s then {дополнительный поток дошел до вершины s}

goto М3;

end;

for v Î V⁺(i) do {пометка по обратным дугам}

begin j:=h1(v);

if g(j)=0 then {т.е. вершина j не помечена}

if x(v) >0 then {по дуге можно пропустить дополнительный поток в обратном направлении}.

begin

g(j):=min (g(i) x(v));

v(j):=-v;

C2:= C2+1; SPW(C2):=j;

if j=s then {дополнительный поток дошел до вершины s}

goto М3;

end;

if С1=C2 then stop; {все помеченные вершины просмотрены, но до вершины s дополнительный поток не дошел, т.е. задача решена, найден максимальный поток}

if C1¹C2 then

begin

С1:=C1+1;

goto М2; {переход на просмотр следующей помеченной вершины}

end;

М3:

begin {по найденному пути из t в s пропускается дополнительный поток}

i=s;

while i ¹ t do

begin

v:=abs (v(i));

if v(i)>0 then

begin

x(v):=x(v)+g(s); {поток прошел по прямой дуге}

i:=h1(v);

end

else

begin

x(v):=x(v)-g(s);{поток прошел по обратной дуге}

i:= h2(s)

end;

goto М1;{переход на поиск нового пути увеличения потока }

end;

end.

Для поиска разреза с минимальной пропускной способностью применим следующий алгоритм.

Алгоритм 2.

begin

Е1:=Æ; E2:=Æ;

for iÎE do

если g(i)>0 then {до вершины i дошел дополнительный поток}

Е1:=E1È{i}

else Е2:=E2È{i};

{E(1) - множество вершин, к которым существует цепь увеличения потока из вершины t, E(2) - множество вершин, к которым такой цепи нет}

V(E1 E2 +):= Æ; V(E1 E2 -):= Æ ;

for vÎV do

begin

if ((h1(v) Î E1 ) and (h2(v) Î E2 )) then

V(E1 E2 +):=V(E1 E2 +) È {v};

if ((h1(v) Î E2) and (h2(v) Î E1 )) then

V(E1 E2 -):=V(E1 E2 -) È {v};

end;

V(E1 E2):=V(E1 E2 +) ÈV(E1 E2 -);

end.

Множество дуг V(E1, E2) составляет разрез с минимальной пропускной способностью.

7.2. Решение задачи о нахождении кратчайших расстояний на графе между двумя вершинами алгоритмами Беллмана-Калабы, Флойда, Дейкстры

Пусть задан ориентированный граф G=<E, V, H>, в котором для каждой дуги vÎV задана длина с(v). На множестве вершин E выделены две вершины t и s. Требуется среди всех путей

t=i(0), v(1), i(1), v(2), i(2), ..., v(k), i(k)=s,

соединяющих вершины t и s,

где h1(v(j))=i(j-1), h2(v(j))=i(j), jÎ[1,...,k]

c длиной

l= S{с(v(j)) | jÎ [1,...,k]},

определить путь, длина которого минимальна .

Обозначим через W(i) длину кратчайшего пути от вершины i до вершины s. Согласно принципу оптимальности Беллмана

W(s)=0,

W(i) = min{c(v)+W(h2(v))| vÎV ^-(i)} iÎE\{s}.

Значение W(t) будет длиной кратчайшего пути от вершины t до вершины s. Для кратчайшего пути

t=i^~(0), v^~(1), i^~(1), v^~(2), i^~(2), ..., v^~(k), i^~(k)=s

справедливо равенство

W(i^~(j-1))=c(v^~(j))+W(i^~(j))=min{c(v)+W(h2(v))|vÎV ^-(i^~(j-1)) }, jÎ[1,...,k].

7.3. Алгоритм Беллмана-Калабы для отыскания кратчайших расстояний на графе между двумя вершинами

⇐ Предыдущая 1 234 5 Следующая ⇒